带头结点的单链表(一)

带头结点的单链表（一）【基本操作训练】——

现有以下定义，你的函数可以直接使用，无需再提交。

#define True 11

#define False 0

#define Ok 111

#define Error -111

#define List_Init_Size 10

#define ListIncrement 10

typedef int Status;//状态类型

typedef struct{

int num;//专家号，不重复，可用于查找专家

char name[30];//专家姓名，可能重复

}ElemType; //元素类型-----专家信息数据类型---------特别关注“数据元素”-------------//

typedef ElemType ET;

typedef struct Lnode{

ElemType data;

struct Lnode *next;

}LNode,*LinkList;

在招投标系统中，专家信息的更新换代比较频繁，假定采用“单链表”结构存储专家信息，请完成以下“带头结点的单链表”的部分基本操作：

（1）（10分）

功能：构造一个带头结点的空单链表 L。

函数名：InitList_L

参数：单链表头指针L

返回值：成功返回Ok；否则，返回Error。

注意：考虑是否引用型参数、参数是怎样的数据类型、返回值类型应当如何? （2）（10分）

功能：求单链表L的长度

函数名：ListLength_L

参数：单链表头指针L

返回值：实际元素个数

注意：考虑是否引用型参数、参数是怎样的数据类型、返回值类型应当如何? （3）（20分）

功能：取表L中的第i个结点值赋值给参数e（注意i的取值范围）

函数名：GetElem_L

参数：单链表头指针L,位置i,数据元素e

返回值：取值成功返回Ok；否则，返回Error。

注意：考虑是否引用型参数、参数是怎样的数据类型、返回值类型应当如何? （4）（20分）Status ListInsert_L(LinkList L , int i , ET e);

功能：在表L的第i个位置上插入一个值为e的数据元素。

返回值：成功返回Ok；否则，返回Error。

（5）（20分）Status ListDelete_L(LinkList L , int i , ET &e);

功能：在表L中删除位序为 i 的数据元素，并将删除的元素赋值给e。

返回值：成功返回Ok；否则，返回Error。

（6）（20分）Status PriorElem_L(LinkList L , ET e , ET &pre_e); 功能：在表L中求元素e的直接前驱元素，并赋值给pre_e。

返回值：成功返回Ok；否则，返回Error。

注意：针对当前的情形，用元素中num成员（比如：e.num）进行比较

注意：

（1）不用编写main函数，函数中没有任何输入输出语句；

（2）所有函数必须同时提交，另外，需要用到特殊的库函数，请自行包含其头文件；否则编译出错；

（3）在 VC 或 VS 环境中调试时，必须建立.CPP源文件。

【【【【【请自主设计“测试程序”，证明你的每一个函数实现了相应功能（以下两个函数有助于测试，不提交）。】】】】】

void printLinkList1(LinkList L)

{

int len=0;

LinkList p=L;

printf("\n单链表的元素为：");

while(p->next){

len++;

p=p->next;

printf("%d ",p->data.num);

}

printf("\n单链表长度len=%d\n",len);

}

void CreateList_L1 (LinkList &L, int n)

//建立一个带头结点的长度为n的单链表L

{

int i;

LinkList p,tail;

L=( LinkList ) malloc ( sizeof ( Lnode ) ); //L指向头结点

tail=L;

printf("\n请输入%d个元素：",n);

for(i=n;i>0; --i)

{

p=( LinkList ) malloc ( sizeof ( Lnode ) ); //p为新结点

scanf("%d",&(p->data.num)); //为结点p的数据域赋值

tail->next=p;tail=p; //将结点p插入到表尾

}

tail-> next = NULL;

}

预设代码

1.#include

2.#include

3.#define True 1

4.#define False 0

5.#define Ok 11

6.#define Error -11

7.typedef int Status;//状态类型

8.typedef struct{

9. int num;//专家号

10. char name[30];//专家姓名

11.}ElemType; //元素类型-----专家信息数据类型

12.typedef ElemType ET;

13.typedef struct Lnode{

14. ElemType data;

15. struct Lnode *next;

16.}LNode,*LinkList;

17.Status InitList_L( LinkList &L);//构造一个空的线性表 L

18.int ListLength_L(LinkList L);

19.Status GetElem_L(LinkList L, int i, ElemType &e);

20.Status ListInsert_L(LinkList L , int i , ET e);

21.Status ListDelete_L(LinkList L , int I , ET &e);

22.int LocateElem_L(LinkList L,ET e);

23.Status PriorElem_L(LinkList L , ET e , ET &pre_e);

24.Status NextElem_L(LinkList L , ET e , ET &next_e);

25.Status InitList_L1( LinkList &L){//构造一个空的线性表 L

26. L=(LinkList)malloc(sizeof(ET));

27. if(L==NULL)

28. return Error;

29. L->next=NULL;

30. return Ok;

31.}

32.Status GetElem_L1(LinkList L, int i, ElemType &e)

33.{

34. return Ok;

35.}

36.Status ListInsert_L1(LinkList L , int i , ET e){

37. LinkList p=L,s;

38. int j=0;

39. while ( p && j< i -1 ){p=p->next; j++;} //寻找

40. if (p==NULL || i<1) return Error;

41. s = ( LinkList ) malloc ( sizeof ( Lnode ) );

42. if (s == NULL) return Error;

43. s->data=e;

44. s->next=p->next ; // 在 p结点之后插入结点s

45. p->next = s ; /* L->data++ ;链表长度计数*/

46. return Ok;

47.}

48.int ListLength_L1(LinkList L)

49.{

50. LinkList p=L;

51. int j=0;

52. while(p->next)

53. {

54. ++j;

55. p=p->next;

56. }

57. return(j);

58.}

59.Status ListDelete_L1(LinkList L , int i , ET &e){

60. if(i<1) return Error;

61. return Ok;

62.}

63.int LocateElem_L1(LinkList L , ET e)

64.{

65. return 0;

66.}

67.Status PriorElem_L1(LinkList L , ET e , ET &pre_e)

68.{

69. return Ok;

70.}

71.Status NextElem_L1(LinkList L , ET e , ET &next_e)

72.{

73. return Ok;

74.}

75.void printLinkL(LinkList L)

76.{

77. LinkList p=L;

78. while(p->next ){

79. p=p->next;

80. printf("%d ",p->data.num);

81. }

82.}

83.void printLinkList1(LinkList L)

84.{

85. int len=0;

86. LinkList p=L;

87. printf("\n单链表的元素为：");

88. while(p->next){

89. len++;

90. p=p->next;

91. printf("%d ",p->data.num);

92. }

93. printf("\n单链表长度len=%d\n",len);

94.}

95.void CreateList_L1 (LinkList &L, int n)

96.//建立一个带头结点的长度为n的单链表L

97. {

98. int i;

99. LinkList p,tail;

100. L=( LinkList ) malloc ( sizeof ( Lnode ) ); //L 指向头结点

101. tail=L;

102.// printf("\n请输入%d个元素：",n);

103. for(i=n;i>0; --i)

104. {

105. p=( LinkList ) malloc ( sizeof ( Lnode ) ); / /p为新结点

106. scanf("%d",&(p->data.num)); //为结点p的数据域赋值

107. tail->next=p;tail=p; //将结点p插入到表头

108. }

109. tail-> next = NULL;

110.}

111.int flag;

112.int main(){

113. LinkList La,Lb;

114. int select;

115. int i=0;

116. ET e;

117. InitList_L1(La);

118. scanf("%d",&i);

119. CreateList_L1 (La,i);

120.// printLinkList1(La);//////////////////////////

121. scanf("%d",&select);

122. switch(select){

123. case 1:{

124. Lb =(LinkList)-1000;

125. i=InitList_L(Lb);

126. Lb->data.num =200;

127. if(Lb->next==NULL && i==Ok){ 128. printf("OK!");

129. }

130. return 0;

131. }

132. case 2:

133. /////////////////////

134. i=ListLength_L(La);

135. if(i==ListLength_L1(La))

136. printf("%d OK!",i);

137. return 0;

138. case 3:{int k;

139. scanf("%d",&k);e.num=9999; 140. i=GetElem_L(La,k,e);

141. if(i==Ok)

142. printf("%d",e.num);

143. else if(i==Error)

144. printf("Error");

145. return 0;

146. }

147. case 4:{int k;ET e={55};

148. scanf("%d",&k);

149. i=ListInsert_L(La,k,e);

150. if(i==Ok )

151. printLinkL(La);

152. else if(i==Error)

153. printf("Error");

154. return 0;

155. }

156. case 5:{int k;ET e;

157. scanf("%d",&k);

158. i=ListDelete_L(La,k,e);

159. if(i==Ok)

160. printLinkL(La);

161. else if(i==Error)

162. printf("Error");

163. return 0;

164. }

165. case 6:{ET e,pre_e;

166. scanf("%d",&e.num);

167. i=PriorElem_L(La,e,pre_e);

168. if(i==Ok)

169. printf("%d",pre_e.num);

170. else if(i==Error)

171. printf("Error");

172. return 0;

173. }

174. }

175. return 0;

176.}

参考答案

1. Status InitList_L(LinkList &L)

2.{

3. L = (LinkList)malloc(sizeof(LNode));

4. if(L == NULL)return Error;

5. L->data.num = 0;

6. L->next = NULL;

7. return Ok;

8.}

9.Status ListLength_L(LinkList L)

10.{

11. LinkList p = L;

12. int j = 0;

13. while(p->next)

14. {

15. ++j;

16. p = p->next;

17. }

18. return j;

19.}

20.Status GetElem_L(LinkList L,int i,ET &

e)

21.{

22. LinkList p = L->next;

23. int j = 1;

24. while(p && j < i)

25. {

26. p = p->next;

27. ++j;

28. }

29. if(!p || j > i)return Error;

30. e = p->data;

31. return Ok;

32.}

33.Status ListInsert_L(LinkList L,int i,ET e)

34.{

35. LinkList s,p = L;

36. int j = 0;

37. while(p && j < i-1)

38. {

39. p = p->next;

40. ++j;

41. }

42. if(!p || j > i-1)return Error;

43. s = (LinkList)malloc(sizeof(LNode));

44. s->data = e;

45. s->next = p->next;

46. p->next = s;

47. return Ok;

48.}

49.Status ListDelete_L(LinkList L, int i, ET &e)

50.{

51. LinkList p = L;

52. int j = 0;

53. while(p->next && j < i-1)

54. {

55. ++j;

56. p = p->next;

57. }

58. if(!p->next || j > i-1)return Error;

59. LinkList q = p->next;

60. p->next = q->next;

61. e = q->data;

62. free(q);

63. return Ok;

64.}

65.Status PriorElem_L(LinkList L,ET e,ET &pre_e)

66.{

67. LinkList q = L;

68. LinkList p = q->next;

69. while(p && p->data.num != e.num)

70. {

71. q = p;

72. p = q->next;

73. }

74. if(!p)return Error;

75. pre_e = q->data;

76. return Ok;

77.}

78.

北京邮电大学 数据结构 实验一 带头结点的单链表构造

数据结构实验报告 实验名称：实验1——单链表的构造 学生姓名：XXXXNB 班级：XXXX 班内序号： 学号：XXXX 日期：XXXXX 1．实验要求 根据线性表的抽象数据类型的定义，完成带头结点的单链表的基本功能。 单链表的基本功能： 1、构造：使用头插法、尾插法两种方法 2、插入：要求建立的链表按照关键字从小到大有序 3、删除 4、查找 5、获取链表长度 6、销毁 7、其他：可自行定义 编写测试main()函数测试线性表的正确性。 2.程序分 编程完成单链表的一般性功能如单链表的构造：使用头插法、尾插法两种方法插入：要求建立的链表按照关键字从小到大有序，删除，查找，获取链表长度，销毁用《数据结构》中的相关思想结合C++语言基本知识编写一个单链表结构。本程序为使用方便，几乎不用特殊的命令，只需按提示输入即可，适合更多的用户使用。 2.1 存储结构 单链表的存储结构：

2.2 关键算法分析 1.头插法 自然语言描述：a.在堆中建立新结点 b.将a[i]写入到新结点的数据域 c.修改新结点的指针域 d.修改头结点的指针域,将新结点加入链表中 //在构建之初为了链表的美观性构造，进行了排序 代码描述： //头插法构造函数 template LinkList::LinkList(T a[], int n) { for (int i = n - 1; i >= 1; i--)//冒泡排序，对数组进行从小到大排序{ for (int j = 0; j < i; j++) { if (a[j]>a[j + 1]) { T t = a[j + 1]; a[j + 1] = a[j]; a[j] = t; } }

c语言 不带头结点的循环链表joseph问题

Joseph问题 题目描述: 原始的Joseph问题的描述如下：有n个人围坐在一个圆桌周围，把这n个人依次编号为1，…，n。从编号是start的人开始报数，数到第num个人出列，然后从出列的下一个人重新开始报数，数到第num个人又出列，…，如此反复直到所有的人全部出列为止。比如当n=6，start=1，num=5的时候，出列的顺序依次是5，4，6，2，3，1。 以下是不带头结点的循环链表算法 */ #include #include typedef int data_t; typedef struct node { data_t data; struct node *next; }listnode, *linklist; /*创建一个不带头节点的循环链表*/ listnode* CreatCycleList(int num) { int i = 2; listnode *head = NULL, *q = NULL, *p = NULL; head = (listnode*)malloc(sizeof(listnode)); head->data = 1; head->next = NULL; p = head; while(i <= num) { q = (listnode*)malloc(sizeof(listnode)); q->data = i; q->next = NULL; p->next = q; p = q; i++; } p->next = head;

return head; } listnode* Joseph(listnode *head, int start, int killNum) { int i; listnode *p, *q;//p遍历链表，q指向待宰的人 p = head; /* 找位置,p最后停在开始报数的前一个人处*/ if(start == 1) { while(p->next != head) { p = p->next; } } else { for(i = 1; i < start-1; i++) { p = p->next; } } /* 开杀*/ while(p != p->next) { for(i = 1; i < killNum; i++) { p = p->next; } q = p->next; p->next = q->next; printf("%d,",q->data); free(q); q = NULL; } return p; }

第三章 单链表 题目和答案

第2章自测卷答案 一、填空 1.顺序表中逻辑上相邻的元素的物理位置相互相邻。单链表中逻辑上相邻的元素的物理位置不 相邻。 2.在单链表中，除了首元结点外，任一结点的存储位置由其直接前驱结点值域指示。 3．在n个结点的单链表中要删除已知结点*p，需找到它的地址。 二、判断正误（在正确的说法后面打勾，反之打叉） 1. 链表的每个结点中都恰好包含一个指针。X 2. 链表的物理存储结构具有同链表一样的顺序。X 3. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。X 4. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。Y 5. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。Y 6. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。X 7. 线性表在物理存储空间中也一定是连续的。X 8. 线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。X 9. 顺序存储方式只能用于存储线性结构。X 10. 线性表的逻辑顺序与存储顺序总是一致的。X 三、单项选择题 （A）1. 链接存储的存储结构所占存储空间： （A）分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 （B）只有一部分，存放结点值 （C）只有一部分，存储表示结点间关系的指针 （D）分两部分，一部分存放结点值，另一部分存放结点所占单元数 （B）2. 链表是一种采用存储结构存储的线性表； （A）顺序（B）链式（C）星式（D）网状 （D）3. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址: （A）必须是连续的（B）部分地址必须是连续的 （C）一定是不连续的（D）连续或不连续都可以 （B）4．线性表Ｌ在情况下适用于使用链式结构实现。 （Ａ）需经常修改Ｌ中的结点值（Ｂ）需不断对Ｌ进行删除插入 （Ｃ）Ｌ中含有大量的结点（Ｄ）Ｌ中结点结构复杂 （C）5．单链表的存储密度 （Ａ）大于1；（Ｂ）等于1；（Ｃ）小于1；（Ｄ）不能确定 （A）6、在单链表的一个结点中有个指针。

数据结构___头插法和尾插法建立链表(各分有无头结点)

实验一链表的建立及基本操作方法实现 一、【实验目的】 、理解和掌握单链表的类型定义方法和结点生成方法。 、掌握利用头插法和尾插法建立单链表和显示单链表元素的算法。 、掌握单链表的查找（按序号）算法。 、掌握单链表的插入、删除算法。 二、【实验内容】 、利用头插法和尾插法建立一个无头结点单链表，并从屏幕显示单链表元素列表。 、利用头插法和尾插法建立一个有头结点单链表，并从屏幕显示单链表元素列表。 、将测试数据结果用截图的方式粘贴在程序代码后面。 重点和难点： 尾插法和头插法建立单链表的区别。 建立带头结点和无头结点单链表的区别。 带头结点和无头结点单链表元素显示方法的区别 三、【算法思想】 ) 利用头插法和尾插法建立一个无头结点单链表 链表无头结点，则在创建链表时，初始化链表指针。 当用头插法插入元素时，首先要判断头指针是否为空，若为空，则直接将新结点赋给,新结点指向空，即>，若表中已经有元素了，则将新结点的指向首结点，然后将新结点赋给即（>）。当用尾插法插入元素时，首先设置一个尾指针以便随时指向最后一个结点，初始化和头指针一样即。插入元素时，首先判断链表是否为空，若为空，则直接将新结点赋给即，若不为空，将最后一个元素的指向新结点即>，然后跳出这个语句，将新结点指向空，并且将指向新结点即>。 ) 利用头插法和尾插法建立一个有头结点单链表 链表有头结点，则在创建链表时，初始化链表指针> 。与无头结点区别在于，判断链表为空是根据>是否为空。 用头插法插入元素时，要判断链表是否为空，若为空则将新结点指向空，作为表尾，若不为空，则直接插入，将新结点指向头结点的指向，再将头结点指向新结点即>>>。 用尾插法插入元素时，首先也要设置一个尾指针以便随时指向最后一个结点，初始化，与无头结点区别就只是插入第一个元素时有区别。插入元素时，不需要判断链表是否为空，直接进行插入，代码>>。 ）带头结点和无头结点单链表元素显示方法的区别： 区别在于，显示时带头结点是从头结点开始即>，而无头结点链表是直接从开始即。 四、【源程序代码】 ) 利用头插法和尾插法建立一个无头结点单链表 <>

数据结构算法习题答案带头结点的循环链表表示队列,并且只设一个指针指向队尾元素结点(注意不设头指针)

数据结构算法题(假设以带头结点的循环链表表示队列,并且只设一个指针指向队尾元素结点(注意不设头指针)试编写相应的队列初始化,入队列和出队列的算法!) (提供两种答案哦！！！) 一： //既然是算法就不用源码了具体看注释 typedef int Datatype; typedef struct queuenode { Datatype data; struct queuenode *next; }QueueNode; //以上是结点类型的定义 typedef struct { queuenode rear; }LinkQueue; //只设一个指向队尾元素的指针 void InitQueue( LinkQueue &Q) { //置空队：就是使头结点成为队尾元素 =(queuenode*)malloc(sizeof(queuenode)) QueueNode* s; Q->rear = Q->rear->next;//将队尾指针指向头结点 while(Q->rear!=Q->rear->next) //当队列非空，将队中元素逐个出队 { s=Q->rear->next; Q->rear->next=s->next; free(s); } //回收结点空间 } int EmptyQueue( LinkQueue &Q) { //判队空 //当头结点的next指针指向自己时为空队 return Q->rear->next->next==Q->rear->next; }

void EnQueue( LinkQueue &Q, Datatype x) { //入队 //也就是在尾结点处插入元素 QueueNode *p=(QueueNode *) malloc (sizeof(QueueNode));//申请新结点 p->data=x; p->next=Q->rear->next;//初始化新结点并链入 Q-rear->next=p; Q->rear=p;//将尾指针移至新结点 } Datatype DeQueue( LinkQueue &Q,Datatype &x) { //出队,把头结点之后的元素摘下 Datatype t; QueueNode *p; if(EmptyQueue( Q )) Error("Queue underflow"); p=Q->rear->next->next; //p指向将要摘下的结点 x=p->data; //保存结点中数据 if (p==Q->rear) { //当队列中只有一个结点时，p结点出队后，要将队尾指针指向头结点 Q->rear = Q->rear->next; Q->rear->next=p->next; } else Q->rear->next->next=p->next;//摘下结点p free(p);//释放被删结点 return x; } 二： typedef struct Node { int data; struct Node *next; }Node,*CiLNode; typedef struct

第三章 链表 基本题

第三章链表 基本题 3.2.1单项选择题 1.不带头结点的单链表head为空的判定条件是 A.head=NULL B.head->next=NULL C.head->next=head D.head!=NULL 2.带头接待点的单链表head为空的判定条件是 A.head=NULL B.head->next=NULL C.head->next=head D.head!=NULL 3.非空的循环单链表head的尾结点(由p所指向)满足 A.p->head=NULL B.p=NULL C.p->next=head D.p=head 4.在循环双链表p的所指结点之后插入s所指结点的操作是 A.p->right=s; s->left=p; p->right->lefe=s; s->right=p->right; B.p->right=s; p->right->left=s; s->lefe=p; s->right=p->right; C.s->lefe=p; s->right=p->right; p->right=s; p->right->left=s; D.s->left=p; s->right=p->right; p->right->left=s; p->right=s; 5.在一个单链表中，已知q所指结点是所指结点p的前驱结点，若在q和p之间插入结点S，则执行 A.s->next=p->next; p->next=s; B.p->next=s->next; s->next=p; C.q->next=s; s->next=p; D.p->next=s; s->next=q; 6.在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行 A.s->next=p; p->next=s; B.s->next=p->next; p->next=s; C.s->next=p->next; p=s; D.p->next=s; s->next=p; 7.在一个单链表中，若删除p所指结点的后续结点，则执行 A.p->next=p->next->next; B.p=p->next; p->next=p->next->next; C.p->next=p->next D.p=p->next->next 8.假设双链表结点的类型如下： typedef struct linknode {int data; /*数据域*/ Struct linknode *llink; /*llink是指向前驱结点的指针域*/ Struct linknode *rlink; /*rlink是指向后续结点的指针域*/ }bnode 下面给出的算法段是要把一个所指新结点作为非空双向链表中的所指结点的前驱结点插入到该双链表中，能正确完成要求的算法段是 A.q->rling=p; q->llink=p->llink; p->llink=q;

带头结点单链表中数据就地逆置

实验3 ：带头结点单链表中数据就地逆置 一、实验目的： 1. 会定义单链表的结点类型； 2. 熟悉对单链表的一些基本操作和具体的函数定义； 3. 了解和掌握单链表的调用格式。 二、实验要求： 1. 认真阅读和掌握实验内容所给的程序，并上机运行； 2. 保存程序运行结果，并结合程序进行分析； 3. 尝试自己调试修改程序并试运行。 三、实验内容： 编写算法实现带头结点单链表的就地逆置，即利用原带头结点单链表的结点空间把数据元素序列逆置。 四、实验程序： #include #include #include typedef int datatype; typedef struct snode { datatype data; struct snode*next; }slnode; sllinitiate(slnode**head); linlistsort(slnode*head); int sllinsert(slnode*head,int i,datatype x); int slldelete(slnode*head,int i,datatype x); int sllget(slnode*head,int i,datatype*x); int sllnotempty(slnode*head); linlistsurt(slnode*head); linlistinsert(slnode*head,datatype x);

converse(slnode*head); main(void) { datatype test[6]={64,6,7,89,12,24}; slnode*head,*p; int n=6,i; sllinitiate(&head); for(i=1;i<=n;i++) sllinsert(head,i,test[i-1]); linlistsort(head); linlistinsert(head,25); converse(head); p=head->next; while(p!=NULL) { printf("%d",p->data); p=p->next; } } sllinitiate(slnode**head) { if((*head=(slnode*)malloc(sizeof(slnode)))==NULL)exit(1); (*head)->next=NULL; } int sllinsert(slnode*head,int i,datatype x) { slnode*p,*q; int j;

不带头结点的单链表head为空的条件

不带头结点的单链表head为空的判别条件是（）A．head!=NULL B．head—>link= =NULL C．head—>link= =head D．head= =NULL B 因为不带头结点,所以head的下一位是第一位 即判断head->link是否为空即可 不带头结点的单链表head为空的判定条件是什么head==NULL;头指针直接指向空 若有头结点，则为head->next==NULL head==null； 带头结点的是head->null; ( )不带头结点的单链表head为空的判定条件是 head==NULL head->next==NULL

head!=NULL head->next==head A head == NULL 带头结点的单链表head为空的判定条件（） 正确答案: B 你的答案: C (错误) head==NULL head->next==NULL head->next==head head!=NULL B 注意是带头结点，如果不带头结点就选A 为何头指针为head的带头结点的单链表判空条件head->next==null?其实一开始这里也是没啥问题的，只是突然产生了疑问点——head为头指针，储存了头结点的地址，按照我残余的一点指针知识，我总感觉不对，head只是个地址，咋可以直接head->next使用呢？其实哈，这里又产生了和我之前学结构体这个知识点一样的纠结点（嘿嘿，其实这里也算是结构体类型）——结构体 总之和结构体类型一样这个指向符号“->”,这里是有特殊规定的，

比如你定义个结构体类型 struct student { int age; float score; char name[100]; }*pstu，stu; 你用stu.age，pstu->age或者(*pstu).age都是一样可以取到成员变量的，这里的pstu它也是个地址，但是c语言就是这么规定了利用pstu->age可以取到其结构体内部成员变量（记住就好）所以不

实验2-不带头结点的单链表

上海电力学院 数据结构实验报告 （2014/2015 学年第2学期）课程编号 250504704 课程名称数据结构 院（系） 专业 班级 学号 姓名 实验名称实验2 不带头结点的单链表 任课老师卢芳芳

实验2 不带头结点的单链表 1【实验目的与要求】 1、熟练掌握动态链表结构及有关算法的设计方法。 2、理解不带表头结点的单链表的特点，掌握其基本操作。 3、熟练掌握运用不带头结点链表表示特定形式的数据的方法，并设计出有关算法。 2【实验内容和步骤】 已知不带头结点的链表结构定义及头插法建表、尾插法建表和打印链表等函数定义如下（详见slnklist.h文件），基于该文件完成实验题1-实验4. #include #include /**************************************/ /* 链表实现的头文件，文件名slnklist.h */ /**************************************/ typedef int datatype; typedef struct link_node{ datatype info; struct link_node *next; }node; typedef node *linklist; /**********************************/ /*函数名称：creatbystack() */ /*函数功能：头插法建立单链表*/ /**********************************/ linklist creatbystack() { linklist head,s; datatype x; head=NULL; printf("请输入若干整数序列:\n"); scanf("%d",&x); while (x!=0) /*以0结束输入*/ { s=(linklist)malloc(sizeof(node)); /*生成待插入结点*/ s->info=x; s->next=head; /*将新结点插入到链表最前面*/ head=s; scanf("%d",&x); } return head; /*返回建立的单链表*/ } /**********************************/ /*函数名称：creatbyqueue() */ /*函数功能：尾插法建立单链表*/ /**********************************/ linklist creatbyqueue() { linklist head,r,s; datatype x; head=r=NULL; printf("请输入若干整数序列:\n"); scanf("%d",&x); while (x!=0) /*以0结束输入*/ { s=(linklist)malloc(sizeof(node));

带头结点的单链表(一)

带头结点的单链表（一）【基本操作训练】—— 现有以下定义，你的函数可以直接使用，无需再提交。 #define True 11 #define False 0 #define Ok 111 #define Error -111 #define List_Init_Size 10 #define ListIncrement 10 typedef int Status;//状态类型 typedef struct{ int num;//专家号，不重复，可用于查找专家 char name[30];//专家姓名，可能重复 }ElemType; //元素类型-----专家信息数据类型---------特别关注“数据元素”-------------// typedef ElemType ET; typedef struct Lnode{ ElemType data; struct Lnode *next; }LNode,*LinkList; 在招投标系统中，专家信息的更新换代比较频繁，假定采用“单链表”结构存储专家信息，请完成以下“带头结点的单链表”的部分基本操作： （1）（10分） 功能：构造一个带头结点的空单链表 L。 函数名：InitList_L 参数：单链表头指针L 返回值：成功返回Ok；否则，返回Error。 注意：考虑是否引用型参数、参数是怎样的数据类型、返回值类型应当如何? （2）（10分） 功能：求单链表L的长度 函数名：ListLength_L 参数：单链表头指针L 返回值：实际元素个数 注意：考虑是否引用型参数、参数是怎样的数据类型、返回值类型应当如何? （3）（20分） 功能：取表L中的第i个结点值赋值给参数e（注意i的取值范围） 函数名：GetElem_L 参数：单链表头指针L,位置i,数据元素e 返回值：取值成功返回Ok；否则，返回Error。 注意：考虑是否引用型参数、参数是怎样的数据类型、返回值类型应当如何? （4）（20分）Status ListInsert_L(LinkList L , int i , ET e);

建立一个带头结点的单向链表,并用随机函数为各结点数据域赋值。

下列给定程序的功能是：建立一个带头结点的单向链表，并用随机函数为各结点数据域赋值。函数fun 的作用是求出单向链表结点(不包括头结点)数据域中的最大值，并且作为函数值返回。 请改正函数fun中的错误，使它能得出正确的结果。 注意：不要改动main函数，不得增行或删行，也不得更改程序的结构。 试题程序： #include #include #include typedef struct as { int data; struct aa *next; }NODE; /********found********/ fun(NODE *h) { int max=-1; NODE *p; p=h; while(p) { if (p->data>max) max=p->data; /********found*******/ p=h->next; } return max; } outresult(int s，FILE *pf) { fprintf(pf,"\nThe max in link: %d\n", s); } NODE *creatlink (int n, init m) { NODE *h,*p,*s; int i; h=p= (NODE*)malloc(sizeof (NODE)); h->data = 9999; for(i=1; i<=n; i++) { s=(NODE*)malloc(sizeof(NODE)); s->data = rand()%m; s->next = p->next; p->next = s; p = p->next; } p->next = NULL; return h; } outlink(NODE *h，FILE *pf) { NODE *p; p=h->next; fprintf(pf,"\nTHE LIST：\n\n HEAD"); while (p) {

带头结点单链表基本操作参考代码

/*线性表抽象数据类型的带头结点单链表实现*/ #include #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define OVERFLOW -2 #define MAXSIZE 100 #define NULL 0 typedef int status; typedef int elemtype; typedef struct lnode{ elemtype data; struct lnode *next; }lnode,*linklist; /*初始化*/ status initlist(linklist *l){ *l=(linklist)malloc(sizeof(lnode)); if(*l) {(*l)->next=NULL; return OK; } else return OVERFLOW; } /*销毁*/ status destroylist(linklist *l){ linklist p; while(*l){ p=*l; *l=(*l)->next; free(p); } return OK; } /*置空*/ status clearlist(linklist *l){ linklist p,q; p=(*l)->next; (*l)->next=NULL; while(p){ q=p; p=p->next; free(q); } return OK;

} /*求单链表长度*/ int listlength(linklist l){ linklist p; int i=0; p=l->next; while(p){ i++; p=p->next; } return i; } /*单链表空否*/ status listempty(linklist l){ if(l->next) return FALSE; else return TRUE; } /*查找*/ int locateelem(linklist l,elemtype e){ int i=0; linklist p; p=l->next; while(p){ i++; if (p->data==e) return i; p=p->next; } return 0; } /*读第i个元素*/ status getelem(linklist l,int i,elemtype *e){ int j=1; linklist p; p=l->next; while(p&&(jnext; } if (!p|| (j>i)) return ERROR; *e=p->data; return OK; } /*求前驱元素*/ status priorelem(linklist l,elemtype cur_e,elemtype *pre_e){

数据结构-带头结点的循环链表

File chainNode.h #ifndef chainNode_ #define chainNode_ template struct chainNode { // data members T element; chainNode *next; // methods chainNode() {next=NULL;} chainNode(const T& element) { this->element = element; this->next=NULL; } chainNode(const T& element, chainNode* next) {this->element = element; this->next = next;} }; #endif File linnerList.h // abstract class linearList // abstract data type specification for linear list data structure // all methods are pure virtual functions #ifndef linearList_ #define linearList_ #include using namespace std; template class linearList { public:

virtual ~linearList() {}; virtual bool empty() const = 0; // return true iff list is empty virtual int size() const = 0; // return number of elements in list virtual T& get(int theIndex) const = 0; // return element whose index is theIndex virtual int indexOf(const T& theElement) const = 0; // return index of first occurence of theElement virtual void erase(int theIndex) = 0; // remove the element whose index is theIndex virtual void insert(int theIndex, const T& theElement) = 0; // insert theElement so that its index is theIndex virtual void output(ostream& out) const = 0; // insert list into stream out }; #endif File circularListWithHeader.h // circularList list with header node and iterator #ifndef circularListWithHeader_ #define circularListWithHeader_ #include #include #include #include"chainNode.h" #include"myExceptions.h" #include"linearList.h" usingnamespace std; template class circularListWithHeader { public: // 构造函数

带头结点的单链表的创建

带头结点的单链表的创建、求表长、输出、插入、删除、查找、逆置 //说明在VC6.0中不能把本代码保存为.c进行编译，应保存为.cpp，原因可能是里边注释是c++的风格，在codeblocks中不存在这个问题 #include #include #define DataType int #define FLAG -1 typedef struct Node { DataType data; struct Node *next; }Lnode,*LinkList; LinkList Creat_LinkList() { LinkList L; Lnode *s,*r; int x; printf("建立有表头结点的单链表，以%d作为创建链表完成的标志\n",FLAG); L=r=s=NULL; L=(Lnode *)malloc(sizeof(Lnode)); if(!L) { printf("表头结点开辟失败\n"); exit(-1); } L->next=NULL; scanf("%d",&x); while(x!=FLAG) { s=(Lnode *)malloc(sizeof(Lnode)); if(!s) { printf("结点开辟失败\n"); exit(-1); }

s->data=x; if(NULL==L->next)//第一个结点的处理 L->next=s; else r->next=s; r=s; scanf("%d",&x); } if(r!=NULL)//对于非空表，最后结点的指针域放空指针r->next=NULL; return L; } /*有头结点的链表，求表长算法*/ int Length_LinkList(LinkList L) { Lnode *p; int j; p=L; j=0; while(p->next) { p=p->next; j++; } return j; } int Print_LinkList(LinkList L) { printf("输出：\n"); Lnode *s; s=L; while(s->next!=NULL) { s=s->next; printf("%3d",s->data);

习题3(链表)

习题3（链表） 一、选择题 （1）链接存储的存储结构所占存储空间（ A ）。 A）分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 B）只有一部分，存放结点值 C）只有一部分，存储表示结点间关系的指针 D）分两部分，一部分存放结点值，另一部分存放结点所占单元数 （2）线性表若采用链式存储结构时，要求内存中可用存储单元的地址（ D ）。 A）必须是连续的 B）部分地址必须是连续的 C）一定是不连续的 D）连续或不连续都可以（3）线性表Ｌ在（ B ）情况下适用于使用链式结构实现。 A）需经常修改结点值 B）需不断删除插入 C）含有大量的结点 D）结点结构复杂（4）单链表的存储密度（ C ）。 A）大于1 B）等于1 C）小于1 D）不能确定 （5）若指定有n个元素的向量，则建立一个有序单链表的时间复杂性的量级是（ C ）。 A）O(1) B）O(n) C）O(n2) D）O(nlog2n) （6）在单链表中，要将s所指结点插入到p所指结点之后，其语句应为（ D ）。 A）s->next=p+1; p->next=s; B）(*p).next=s; (*s).next=(*p).next; C）s->next=p->next; p->next=s->next; D）s->next=p->next; p->next=s; （7）在双向链表存储结构中，删除p所指的结点时须修改指针（ A ）。 A）p->next->prior=p->prior; p->prior->next=p->next; B）p->next=p->next->next; p->next->prior=p; C）p->prior->next=p; p->prior=p->prior->prior; D）p->prior=p->next->next; p->next=p->prior->prior; （8）在双向循环链表中，在p指针所指的结点后插入q所指向的新结点，其修改指针的操作是（ C ）。 A）p->next=q; q->prior=p; p->next->prior=q; q->next=q; B）p->next=q; p->next->prior=q; q->prior=p; q->next=p->next; C）q->prior=p; q->next=p->next; p->next->prior=q; p->next=q; D）q->prior=p; q->next=p->next; p->next=q; p->next->prior=q; （9）链表可以带表头结点，也可以不带表头结点，前者最主要的好处是（ B ）。 A）加快表的遍历 B）使空表和非空表的处理统一 C）节省存储空间 D）提高存取元素的速度（10）在单链表指针p所指向的结点后面插入一个新结点q的操作语句序列为（ A ）。 A）q->next=p->next; p->next=q; B）p=p->next; p->next=q->next; C）q=p->next; q->next=p->next; D）p->next=q; q->next=p->next; （11）在一个单链表中,若要删除p个结点的后继结点,则执行( A ) A）p->next=p->next->next; B）p=p->next; p->next->next; C）free（p->next）; D）p＝p->next->next； （12）设rear是指向非空带头结点的循环单链表的尾指针，则删除表首结点的操作可表示为( B ) A）p＝rear; B）p= rear->next->next; Rear=rear->next; rear->next->next＝p->next; free(p); free(p); C）rear:=rear->next->next; D）rear＝rear->next free(rear); free(rear);

建立不带头结点单链表的4种方法

C语言写的建立不带头结点的单链表的4种方法，前2种有问题，后2种正确。可以帮助学习理解单链表出错的原因和如何建立单链表 #include #include #define ElemType int #define Status int #define SUCCESS 1 #define ERROR 0 struct node { ElemType data; struct node *next; }; typedef struct node *List; typedef struct node *ptrNode; Status List_Create(List La,int len); Status List_Create2(List La,int len); Status List_Create3(List *La,int len); List List_Create4(int len); void List_Printf(List La); void List_FreeWithNode(List La); void List_FreeWithoutNode(List La); void DisplayCreateList(); int main() { List header=NULL; int len; int choose; Status s=SUCCESS; printf("\n*********输入链表长度**********\n"); scanf("%d",&len); do { DisplayCreateList(); scanf("%d",&choose); }while(choose <1 || choose>4); switch(choose)

把一个带头结点的单链表所有数据结点逆置

#include typedef int ElemType; struct LinkList { ElemType data; LinkList *next; }; void Initial(LinkList *&L) //单链表的初始化{ L=new LinkList; L->next=NULL; } void LinkInsert(LinkList *&L,ElemType e) //插入结点{ LinkList *p=L; while(p->next!=NULL) { p=p->next; } LinkList *s; s=new LinkList; s->data=e; s->next=p->next; p->next=s; } void Input(LinkList *&L) //输入单链表 { cout<<"请输入10个数存入："<>e; LinkInsert(L,e); } } void DisplayLink(LinkList *&L) { LinkList *p=L; while(p->next!=NULL) { cout<next->data<<"\t"; p=p->next; } cout<

} void oppverse(LinkList *&L) //逆置所有结果、点{ LinkList *p=L,*q,*s; while(p->next!=NULL) { s=p->next; p=p->next; } p=L; q=L->next; ElemType temp; while(p->next!=s) { temp=s->data; s->data=q->data; q->data=temp; q=q->next; while(p->next!=s) { p=p->next; } s=p; p=q; } } void main() { LinkList *L; Initial(L); Input(L); DisplayLink(L); oppverse(L); cout<<"逆置后的单链表为："<