【数据结构笔记备忘】单链表，双向链表，循环单双链表_哪些排序用到单链,双链,循环链

参考书籍《数据结构第二版——严蔚敏》

笔记暂时纪录在这，后续如果有改进和修改会同步更新

大部分的说明性语言都在注释中
数据结构定义说明

typedef struct {
	int name;
	char num[50];
	int ssd;
}data;//数据域的结构类型
typedef struct link {//单链表的数据结构
	data Ldata;
	struct link* next;//好像这里不能用LNode来定义，因为这就是在定义LNode
}LNode, * LinkList;//把这种链表的指针类型定义为LinkList，和下面那种typedef一样的效果

//LNode* pp;//通常这个pp用来指向链表的头节点，或者第一个元素也可用LinkList pp定义，两者一样
//typedef LNode* LinkList;

/*
双向链表的构造及数据结构
prior是前驱指针
*/
typedef struct Dulink {
	data Ldata;
	struct Dulink* next, * prior;
}DuLNode, * DuLinkList;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

然后是一些单链表，双向链表，循环链表的一些常用的操作函数，这里注释只是简单说明，在具体实现时会有更详细的说明。

//三个单链表的初始化方式
int List_init1(LinkList& L);//如果时此方式 则应该List_init1(pp);
LNode* List_init2(void);//如果是此方式，则应该pp=List_init2();
int List_init3(LinkList* L);//如果时此方式 则应该List_init3(&pp);
//单链表的一些常用函数
int ListEmpty(LinkList L);//判断一个单链表是否为空表
int DestoryList_L(LinkList& L);//销毁单链表
int ClearList(LinkList& L);//清空一个单链表
int GetElem_L(LinkList L, int i, data& data);//获取某个节点的数据区，通过data接收
int ListLength(LinkList L);//返回链表的长度.i=0,则不算头节点，i=1，则算头节点
LNode* LocateElem_L_P(LinkList L, int nam);//在单链表中按照数据域中的某个值来查找响应节点，返回对应节点的地址
LNode* LocateElem_LN_P(LinkList L, int n);//在单链表中按照第几个节点来查找响应节点，返回对应节点的地址
int LocateElem_L_N(LinkList L, int nam);//在单链表中按照数据域中的某个值来查找响应节点，返回对应节点的序号
int ListInsert_L(LinkList& L, int i, data dat);//在第i个节点之前插入一个新节点
int ListDelete_L(LinkList& L, int i, data& dat);//将链表中第i个元素删除
int CreateList_H(LinkList& L, data& dat);//用头插法来建立一个链表
int CreateList_R(LinkList& L, data& dat);//用尾插法来建立一个链表

//双向链表的一些函数
LinkList ConnectList_R(LinkList Ta, LinkList Tb);//将两个尾指针循环链表相互连接
int ListLength_Du(DuLinkList L);//返回双向链表的长度.i=0,则不算头节点，i=1，则算头节点
DuLNode* LocateElem_LN_P_Du(DuLinkList L, int n);//在双向链表中按照第几个节点来查找相应节点，返回对应节点的地址
int ListInsert_DuL(DuLinkList& L, int i, data dat);//双向链表的插入,在第i个节点之前插入
int ListDelete_DuL(DuLinkList& L, int i, data dat);//双向链表的删除,删除第i个节点，并用dat接取删除节点的数据域
DuLNode* List_init2_Du(void);//初始化一个双向链表节点（分配内存）

void MergeList_L(LinkList& LA, LinkList& LB, LinkList& LC);//有序单链表的合并，将LA，LB合并到LC
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

以上函数的具体实现方式

/*初步理解,这个函数的作用就类似，如果你在函数外定义a=10，函数形参b，传入参数a，（f（a）；）此时
在函数内部你将b=3，当你出了这个函数，会发现a的值并没有改变，所以通常我们就直接取a的地址传入，通过*b修改
在为指针分配内存也是一样，如果直接传入在出了函数之后分配的内存就会被回收。所以用下面这个方法来为这个
空指针分配内存
除此之外还能有两种方法，
一 使用二级指针，如 int List_init3(LinkList *L)；
二 函数返回值为一个分配好内存的指针，使用时将返回值赋值给pp空指针即可
   如LNode* List_init2（）； 使用时 令 pp=List_init2（）；
*/
int List_init1(LinkList& L) {//作用就是为你自己定义的指针分配一块内存（注意引用&是c++中的语法，在C语言中要以指针替换）
	/*这里想到一个问题，如果这个L指针已经被分配了内存那么再次分配会如何
	查阅资料得知，这样会导致系统找不到第一次分配的内存的地址，从而造成内存泄露
	长时间如此会造成可用内存越来越少，最终导致系统崩溃
	*/
	if (L) return 1;//内存已经被分配了内存，跳过分配
	L = (LinkList)malloc(sizeof(LNode));//如果时此方式 则应该List_init1(pp);
	if (!L)  return 0;//内存不足分配失败
	else {
		L->next = NULL;
		return 1;
	}
}
LNode* List_init2(void) {//如果是此方式，则应该pp=List_init2();为了避免二次分配造成内存泄露，要在调用之前单独判断接收的指针是否被分配内存
	LinkList p;
	p = (LinkList)malloc(sizeof(LNode));
	if (!p) return 0;//内存不足分配失败
	else {
		p->next = NULL;
		return p;
	}
}
int List_init3(LinkList* L) {//如果时此方式 则应该List_init3(&pp);
	if (*L) return 1;//内存已经被分配了内存，跳过分配
	*L = (LinkList)malloc(sizeof(LNode));
	if (!(*L))  return 0;//内存不足分配失败
	else {
		(*L)->next = NULL;
		return 1;
	}
}
/*在这里补充一些知识点
  free函数只是将参数指针指向的内存归还给操作系统，并不会把参数指针置NULL，
  为了以后访问到被操作系统重新分配后的错误数据，所以在调用free之后，通常需要手动将指针置NULL。
  从另一个角度来看，内存这种底层资源都是由操作系统来管理的，而不是编译器，编译器只是向操作系统提出申请。
  所以free函数是没有能力去真正的free内存的。只是告诉操作系统它归还了内存，然后操作系统就可以修改内存分配表，
  以供下次分配。

  free一个空指针是可以的，当释放空指针时该函数不会做任何事情
  但是释放野指针是不可以的，当第一次free了一个指针之后，这个指针所指的空间就被释放掉了，但是这个指针仍然会指向
  这个地址，如果不小心再次free了这个指针那么就会造成 double free错误，将一个指针释放两次确实是非常危险的行为，
  它可以造成任意代码执行

  free(str)后指针仍然指向原来的堆地址，即你仍然可以继续使用，但很危险，因为操作系统已经认为这块内存可以使用，
  他会毫不考虑的将他分配给其他程序，于是你下次使用的时候可能就已经被别的程序改掉了，这种情况就叫“野指针”，
  所以最好free（）了以后再置空
  造成“野指针”的原因主要有

	1.指针变量没有初始化，任何指针变量刚被创建时不会自动成为NULL指针，它的缺省值是随机的，它会乱指一气。
	  在初始化的时候要么指向合法的指针，要么指向NULL。

	2.指针变量被free或delete之后，没有设置为NULL。它们只是把指针所指的内存给释放掉，但并没有把指针本身干掉。通常会用语句if (p != NULL)进行防错处理。
	  很遗憾，此时if语句起不到防错作用，因为即便p不是NULL指针，它也不指向合法的内存块。

	3.指针操作超越了变量的作用范围。 注意其生命周期。

	补充：
	struct stuff{
	char *home;
	int num;
	char name[10];
	};

	struct stuff{
	char home[10];
	int num;
	char name[10];
	};

	以上两种结构体，第一种如果给home分配了内存，如果只释放结构体的指针，那home申请到的内存并不会被释放，
	第二种则不会出现这种情况。free()只能释放指针所指向的那片内存。也就是说，如果我们不断地声明第一种类型的结构体的话，
	即使调用free()也会造成内存的浪费。最明显的应该是体现在链表类结构
*/



int ListEmpty(LinkList L) {//判断一个单链表是否为空表
	if (L->next == NULL)
		return 1;//表示为空
	else
		return 0;
}
int DestoryList_L(LinkList& L) {//销毁单链表
	LNode* p;//或者LinkList p
	while (L) {//L!=NULL
		p = L;//先将L指向的结点给P
		L = L->next;//然后L指向下一个节点
		free(p);//删除刚刚的节点
	}//循环直到L指向空（NULL）
	return 1;
}

int ClearList(LinkList& L) {//清空一个单链表
	LNode* p, * q;//定义两个中间变量指针
	p = L->next;//指向第一个节点   p=L为首元节点
	q = p;//这一步是为了避免报错，先将q给一个初值
	while (p != NULL) {//或者条件为p也行
		q = q->next;//q提前指向下一个
		free(p);//释放p
		p = q;//此时如果指向的下一个为空则结束循环，不为空则继续
	}
	L->next = NULL;//第一个节点已经被释放，将头节点的next设置为空
	return 1;
}


int GetElem_L(LinkList L, int i, data& data) {//获取某个节点的数据区，通过data接收
	LinkList p;//中间指针变量
	int j = 0;//用于记录找到第几个节点了
	p = L->next;//首先指向第一个节点,即这里不算首元节点，将我们定义的第一个当作第一个节点
	j = 1;
	while (p && j < i) {//一直往下找，直到这俩条件有一个不成立，即 p为空或者 i==j
		/*题外话，这里开始我将j<i写成i<j了，可让我好找这个该死的bug*/
		p = p->next;
		j++;
	}
	if (!p || j > i)//这里已经退出循环，这俩条件有一个成立就代表没找到，出错了，即 p为空或者 j>i(i=-1,0等不合法数值)
		return 0;
	data = p->Ldata;//返回当前节点的数据区，由data接收
	return 1;
}

//返回链表的长度.i=0,则不算头节点，i=1，则算头节点
int ListLength(LinkList L) {
	LNode* p;
	int i = 0;
	p = L->next;
	while (p) {
		p = p->next;
		i++;
	}
	return i;
}
LNode* LocateElem_L_P(LinkList L, int nam) {//在单链表中按照数据域中的某个值来查找响应节点，返回对应节点的地址
	//这里举例查找data中name的值
	LNode* p;
	p = L->next;
	while (p && p->Ldata.name != nam) {
		p = p->next;
	}
	return p;//这一步如果找到了刚好返回的是对应节点的地址，如果没找到刚好是NULL
}

LNode* LocateElem_LN_P(LinkList L, int n) {//在单链表中按照第几个节点来查找响应节点，返回对应节点的地址
	LNode* p;
	p = L->next;//指向第一个节点
	int i = 1;
	while (p && i < n) {
		p = p->next;
		i++;
	}
	return p;//这一步如果找到了刚好返回的是对应节点的地址，如果没找到刚好是NULL
}

int LocateElem_L_N(LinkList L, int nam) {//在单链表中按照数据域中的某个值来查找响应节点，返回对应节点的序号
	//这里举例查找data中name的值
	LNode* p;
	p = L->next;
	int j = 1;
	while (p && p->Ldata.name != nam) {
		p = p->next;
		j++;
	}
	if (p) return j;//如果p不为空则是找到了，返回对应的序号
	else  return 0;//反之返回0，表示没找到
}
/**
  * @brief 在第i个节点之前插入一个新节点
  *       （注意引用&是c++中的语法，在C语言中要以指针替换）
  * @param  i: 表示第几个节点
  * @param  dat: 用dat来存储增加节点数据域的数据
  * @retval 0 错误 1成功
  */
int ListInsert_L(LinkList& L, int i, data dat)//，数据域用传入的dat
{
	LNode* p;
	int j = 0;
	p = L;//p指向首元节点
	while (p && j < i - 1) {
		p = p->next;
		j++;
	}
	if (!p || j > i - 1) return 0;
	LNode* s;
	s = (LinkList)malloc(sizeof(LNode));
	if (s == NULL) return 0;
	s->Ldata = dat;
	s->next = p->next;//将新建的节点指向后面的节点，把原来i位置的后面的地址赋值
	p->next = s;//将原来i位置的节点指向新建的节点
	return 1;
}
/**
  * @brief 将链表中第i个元素删除
  *       （注意引用&是c++中的语法，在C语言中要以指针替换）
  * @param  i: 表示删除第几个元素
  * @param  dat: 用dat来存储被删除数据的数据域
  * @retval 0 错误 1成功
  */
int ListDelete_L(LinkList& L, int i, data& dat) {//将链表中第i个元素删除，用dat来存储被删除数据的数据域
	LNode* p, * q; int j = 0;
	p = L;
	while (p->next && j < i - 1) {
		p = p->next;
		j++;
	}
	if (!(p->next) || j > i - 1) return 0;
	q = p->next;//保存被删除节点的地址
	p->next = q->next;//将前驱节点指向后面的节点
	dat = q->Ldata;//保存被删除节点的数据域
	free(q);//释放内存
	return 1;
}

/**
  * @brief 用头插法来建立一个链表,这里我做了一些修改
  *        原版是在函数内部给 L分配空间，这里我并没有这样做
  *        因此在使用该函数之前必须要调用List_init（）来为L分配空间
  *       （注意引用&是c++中的语法，在C语言中要以指针替换）
  * @param  L: LNode*  pp 定义的一个指针，指向头节点
  * @param  dat: data 类型的数据域结构体，用于给新建节点的数据域赋值
  * @retval 0 错误 1成功
  */
int CreateList_H(LinkList& L, data& dat) {
	if (L == NULL)//检查L是否为空
		return 0;//表示传入的L并没有分配空间
	LinkList p;
	p = (LinkList)malloc(sizeof(LNode));//创建一个新节点
	if (p == NULL) return 0;
	p->Ldata = dat;//将数据放入数据域
	p->next = L->next;//将头节点之后的元素放到新建节点后
	L->next = p;//将新节点放入头节点后
	return 1;
}
/**
  * @brief 用尾插法来建立一个链表,
  *        原版是在函数内部给 L分配空间，这里我并没有这样做
  *        因此在使用该函数之前必须要调用List_init（）来为L分配空间
  *       （注意引用&是c++中的语法，在C语言中要以指针替换）
  * @param  L: LNode*  pp 定义的一个指针，指向头节点
  * @param  dat: data 类型的数据域结构体，用于给新建节点的数据域赋值
  * @retval 0 错误 1成功
  */
int CreateList_R(LinkList& L, data& dat) {
	if (L == NULL)//检查L是否为空
		return 0;//表示传入的L并没有分配空间
	LinkList p;//新建的节点
	LNode* q; //用来寻找最后一个节点
	q = L;
	p = (LinkList)malloc(sizeof(LNode));//创建一个新节点
	if (p == NULL) return 0;//创建新节点失败
	p->Ldata = dat;//将数据放入数据域
	p->next = NULL;//将新建节点的后继指针置空
	while (q->next) {//找到最后一个节点
		q = q->next;
	}
	q->next = p;//将新建的节点接在后面
	return 1;
}
/*
构造循环链表将最后一个节点的后继指向首元节点即可
尾指针循环链表即L指向最后一个节点而不是首元节点，然后还是循环链表
*/

/**
  * @brief 将两个尾指针循环链表相互连接
  * @param  Ta:第一个循环链表的尾指针
  * @param  Tb:第二个循环链表的尾指针（保留为合并循环链表的尾指针）
  * @retval 0 错误 1成功
  */
LinkList ConnectList_R(LinkList Ta, LinkList Tb) {
	LinkList p;
	p = Ta->next;//保存ta的首元节点的地址
	Ta->next = Tb->next->next;//将tb的第一个节点连到ta后面
	free(Tb->next);//释放tb的首元节点
	Tb->next = p;//将tb的后继连到ta的首元节点
	return Tb;
}


//返回双向链表的长度.i=0,则不算头节点，i=1，则算头节点
int ListLength_Du(DuLinkList L) {
	DuLNode* p, * q;
	int i = 0;
	q = L;//记录头节点的地址
	p = L->next;
	while (!(p == q)) {
		p = p->next;
		i++;
	}
	return i;
}
/**
  * @brief 在双向链表中按照第几个节点来查找相应节点，返回对应节点的地址，
  *        注意这个算法并没有加入计算双向链表的长度，也就是说在要查找的大于循环链表的
  *        长度时，会从新回到首元节点继续算。
  * @param  L:要操作的双向链表
  * @param  i:第几个节点
  * @retval 对应节点的地址
  */
DuLNode* LocateElem_LN_P_Du(DuLinkList L, int n) {
	DuLNode* p;
	p = L->next;//指向第一个节点
	int i = 1;
	while (p && i < n) {
		p = p->next;
		i++;
	}
	return p;//这一步如果找到了刚好返回的是对应节点的地址，如果没找到刚好是NULL
}

/**
  * @brief 双向链表的插入,在第i个节点之前插入
  * @param  L:要操作的双向链表
  * @param  i:第几个节点
  * @param  dat:新建节点数据域的数据
  * @retval 0 错误 1成功
  */
int ListInsert_DuL(DuLinkList& L, int i, data dat) {
	DuLNode* p;
	p = LocateElem_LN_P_Du(L, i);
	if (!p) return 0;//防止返回空指针，我寻思一般也不会返回空
	DuLNode* s;//新建节点
	s = List_init2_Du();//初始化一个新建节点
	s->Ldata = dat;//将数据放入新建节点
	s->prior = p->prior;//连接前驱
	p->prior->next = s;//将原本前驱节点的后继从指向p换成新建节点s
	s->next = p;//将新建节点的后继改成p
	p->prior = s;//将原本p的前驱换成s
	return 1;
}
/**
  * @brief 双向链表的删除,删除第i个节点，并用dat接取删除节点的数据域
  * @param  L:要操作的双向链表
  * @param  i:第几个节点
  * @param  dat:用来接取删除节点数据域的结构体
  * @retval 0 错误 1成功
  */
int ListDelete_DuL(DuLinkList& L, int i, data dat) {
	DuLNode* p;
	p = LocateElem_LN_P_Du(L, i);
	if (!p) return 0;//防止返回空指针，我寻思一般也不会返回空
	dat = p->Ldata;//接取数据
	p->prior->next = p->next;
	p->next->prior = p->prior;
	free(p);
	return 1;
}
//初始化一个双向链表节点（分配内存）
DuLNode* List_init2_Du(void) {//如果是此方式，则应该pp=List_init2_Du();
	DuLinkList p;
	p = (DuLinkList)malloc(sizeof(DuLNode));
	if (!p) return 0;
	else {
		p->next = NULL;
		p->prior = NULL;
		return p;
	}
}

/**
  * @brief 有序单链表的合并，将LA，LB合并到LC（本函数仅做举例，按照数据域中的name来进行排序）
  * @param  LA:SqList
  * @param  LB:SqList  LB在合并结束之后头节点被释放
  * @param  LC:SqList  这里LC应该是一个未分配内存的指针，因为在函数内部这个指针被指向了LA
  * @retval NULL
  */
void MergeList_L(LinkList &LA, LinkList& LB, LinkList& LC) {
	LinkList pa = LA->next,
			pb = LB->next,//这两条让pa，pb分别指向第一个节点
			pc = LC = LA;//用LA的头节点作为LC的头节点
	while (pa&&pb) {//两个中有一个为零，即找到最后一个元素就停止
		if (pa->Ldata.name <= pb->Ldata.name) {
			pc->next = pa;//将较小的接到pc后面
			pc = pa;//pc指针向后移，相当于pc=pc->next;
			pa = pa->next;//在这里pa所指的已经被连入pc，所以要向后移一个，以便下一次比较
		}
		else {//遇上同理
			pc->next = pb;
			pc = pb;
			pb = pb->next;
		}
	}
	pc->next = pa ? pa : pb;//这里判断pa是否为空，为空则表示pa即LA已经到底，则pc->next=pb，将pb剩余节点接入pc，反之亦然
	free(LB);//释放LB的头节点
}

void Merge_LinkedList_C(LinkList* La, LinkList* Lb, LinkList* Lc) {//这是c语言版，供参考
	*Lc = *La; //让Lc使用La的头节点进行合并
	LinkList pa = (*La)->next, pb = (*Lb)->next; // pa, pb分别表示合并时所指节点
	LinkList pc = *Lc; // pc表示Lc的尾节点
	while (pa && pb) {
		if (pa->Ldata.name < pb->Ldata.name) {
			pc->next = pa;
			pc = pa;
			pa = pa->next;
		}
		else {
			pc->next = pb;
			pc = pb;
			pb = pb->next;
		}
	}
	pc->next = pa ? pa : pb;// pc->next不需要NULL,因为合并时一定会剩下一串节点，只需指向该剩下的节点就OK
	free(*Lb);
	*La = *Lb = NULL;//这一句，因为Lb被释放指针置空以免误操作未分配内存，La分配的内存空间已经给了Lc，所以它也没用了清空以便下次使用
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416

两个简单的单链表应用

void test_List1() {//单链表 示例1
	/*问题引入
	 解决稀疏多项式的合并问题,这里是顺序的多项式，不顺序的要稍稍麻烦一点
	 Pa(x)=7 +3x           +9x^8+ 5x^17
	 Pb(x)=   8x  +22x^7   -9x^8
	 这边我就懒得修改之前的数据结构了
	 就按数据域name代表几次，ssd代表系数
	 */
	LNode* pp;//单链表
	pp = List_init2();

	data dat;//这里结构体的赋值还是老老实实来，data dat{1,2,3}这样出来结果不对，定义结束，dat={1，2，3}这样也不对
	dat.name = 0; dat.ssd = 7;
	CreateList_R(pp,dat);//用尾插法来建立一个链表
	dat.name = 1; dat.ssd = 3;
	CreateList_R(pp, dat);
	dat.name = 8; dat.ssd = 9;
	CreateList_R(pp, dat);
	dat.name = 17; dat.ssd = 5;
	CreateList_R(pp, dat);

	LNode* pp1;//单链表
	pp1 = List_init2();

	dat.name = 1; dat.ssd = 8;
	CreateList_R(pp1, dat);
	dat.name = 7; dat.ssd = 22;
	CreateList_R(pp1, dat);
	dat.name = 8; dat.ssd = -9;
	CreateList_R(pp1, dat);

	/*这里处理呢 有两种方法，一是从新建立一个链表，将算好的结果存入，
	二是就用这俩个链表改变头尾指针从新组合成一个新的链表。还有可能造成内存泄露，所以我选择
	第一种方法，如果不需要原来的数据，则可以在运算结束之后销毁原来的链表，这样来说时间复杂度和
	空间复杂度都相对较高，但是比较稳*/

	LNode* pp2;//单链表
	pp2 = List_init2();

	LNode* p1, *p2;
	p1 = pp->next;//分别指向第一个元素
	p2 = pp1->next;
	while (p1&&p2) {//如果有一个指到了最后
		printf("name1=%d ssd1=%d  name2=%d ssd2=%d\n", p1->Ldata.name, p1->Ldata.ssd, p2->Ldata.name, p2->Ldata.ssd);
		printf("当前链表长度%d\n", ListLength(pp2));
		if (p1->Ldata.name<p2->Ldata.name) {//比较次数大小小的放入新链表中，并将小的后移
			CreateList_R(pp2, p1->Ldata);
			p1 = p1->next;
		}
		else if (p1->Ldata.name == p2->Ldata.name) {//相等则系数相加，两个都后移
			dat.name = p1->Ldata.name;
			dat.ssd = p1->Ldata.ssd + p2->Ldata.ssd;
			if (dat.ssd) //如果系数和不为零则加入新链表，
			  CreateList_R(pp2,dat);
			p1 = p1->next;
			p2 = p2->next;
		}
		else {
			CreateList_R(pp2, p2->Ldata);
			p2 = p2->next;
		}
	}
	printf("p1=%p   p2=%p\n",p1,p2);
	if (p1) 
			while (p1) {
				CreateList_R(pp2, p1->Ldata);
				p1 = p1->next;
			}
			
		
		else 
			while (p2){
				CreateList_R(pp2, p2->Ldata);
				p2 = p2->next;
			}
	/*到此所有工作已经做完，下面是打印工作*/
	p1 = pp2->next;
	while (p1){
		printf("次数%d   系数%d\n",p1->Ldata.name,p1->Ldata.ssd);
		p1 = p1->next;
	}

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

以上示例的运行结构如下
示例二

void test_List2() {//单链表 示例1
	/*一个简单的图书管理系统，可以做到图书的录入，然后根据图书的名称查找书的编号和价格
	这边呢，为了省事我也就还是继续使用之前的那个数据结构了
	typedef struct {
	int name;
	char num[50];
	int ssd;
    }data;
	就是这个数据域的结构
	这里用num[]数组来存储书籍的名字，用name存储书籍的编号，用ssd来存储书籍的价格
	*/
	LNode* pp;//单链表
	pp = List_init2();

	data dat = {0,0,0};
	printf("&dar=%p\n", &dat);

	DataSet(1,"hello world",50,& dat);
	CreateList_R(pp, dat);
	DataSet(2, "斗破苍穹", 80, &dat);
	CreateList_R(pp, dat);
	DataSet(3, "数据结构", 20, &dat);
	CreateList_R(pp, dat);
	DataSet(4, "C语言", 36, &dat);
	CreateList_R(pp, dat);
	DataSet(5, "巴拉达", 87, &dat);
	CreateList_R(pp, dat);
	printf("当前链表长度%d\n", ListLength(pp));

	LNode* p;
	p=LocateElem_L_P_Char(pp,"斗破苍穹");

	printf("p->Ldata.name=%d   p->Ldata.nam=%s\n", p->Ldata.name, p->Ldata.num);

	char book[50];
	printf("请输入要查询的书籍\n");
	scanf_s("%s",book,50);
	p = LocateElem_L_P_Char(pp,book);
	if (p) {
		printf("已经查到所找的书籍...\n编号为%d 名称%s 价格为%d元\n", p->Ldata.name, p->Ldata.num, p->Ldata.ssd);
	}
	else
		printf("对不起要查询的书籍不存在...");

	printf("示例结束");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

以上示例的运行结果如下（输入“斗破苍穹”）