北林 数据结构期末考试(五) 算法设计题

数据结构数据结构 算法设计算法设计题题 天涯古巷天涯古巷 出品出品 必考：链表必考：链表 题型一：题型一：单链表的定义单链表的定义 #include #include #define datatype int/int可换成其他（eg：结构体） typedef struct node datatype data; struct node *next; /自引用 LNode,*LinkList; 题型二题型二：单链表的创建单链表的创建 方法一：头部插入结点创建单链表方法一：头部插入结点创建单链表（不带头结点）（不带头结点） #define flag 0 void Create_LinkList(LinkList L) /单链表L不带头结点 L=NULL;/初始化表头为NULL LNode *Node;/定义结点 datatype data; scanf(%d, while (data!=flag)/设flag为输入结束标志 Node=(LNode *)malloc(sizeof(LNode);/为插入元素申请空间 Node-data=data;/将插入元素置入申请到得单元中 Node-next=L; L=Node;/表头L指向新结点 scanf(%d, /读入数据顺序与线性表中逻辑顺序相反 输入顺序：输入顺序：（25, 45, 18, 76, 2925, 45, 18, 76, 29） 方法二：尾部插入结点创建单链表（不带头结点）方法二：尾部插入结点创建单链表（不带头结点） void Create_LinkList(LinkList L) /单链表L不带头结点 L=NULL;/初始化表头为NULL LNode *Node; LNode *R=NULL;/需加指针R用来始终指向链表尾结点 datatype data; scanf(%d, while (data!=flag)/设flag为输入结束标志 Node=(LNode *)malloc(sizeof(LNode);/为插入元素申请空间 Node-data=data;/将插入元素置入申请到得单元中 if(L=NULL) L=Node;/因为L没有开辟空间，所以L指向新开结点Node的数据域 else R-next=Node; R=Node; scanf(%d, if (R!=NULL) R-next=NULL; /读入数据顺序与线性表中逻辑顺序相同 输入顺序：输入顺序： （25, 45, 18, 76, 2925, 45, 18, 76, 29） 方法二：尾部插入结点创建单链表（带头结点）方法二：尾部插入结点创建单链表（带头结点） #define flag 0 void Create_LinkList(LinkList L) /单链表L带头结点 L=NULL;/初始化表头为NULL LNode *Node;/定义结点 LNode *R=NULL;/需加指针R用来始终指向链表尾结点 L=(LinkList)malloc(sizeof(Node);/申请头结点空间 L-next=NULL; R=L; datatype data; scanf(%d, while (data!=flag)/设flag为输入结束标志 R-next=malloc(sizeof(LNode); R-next-data=data; R=R-next; scanf(%d, R-next=NULL; /读入数据顺序与线性表中逻辑顺序相同 题型三题型三：单链表求表长（线性表的长度不包括头结点）单链表求表长（线性表的长度不包括头结点） int Length_LinkList(LinkList L) LNode *p=L; int j=0;/(L带头结点则令j=0；L不带头结点则令j=1) if (p=NULL) return 0;/表空 while (p-next!=NULL) p=p-next; j+; return j; 题型四题型四：单链表插入单链表插入 方法一：后方法一：后插法（新结点插法（新结点* *S S 插入到结点插入到结点*p*p 后面）后面） S=(LNode S=(LNode *)malloc(sizeof(LNode);*)malloc(sizeof(LNode); S S- -next=pnext=p- -next;next; p p- -next=S;next=S; 方法二：前插法（新结点方法二：前插法（新结点*S*S 插入到结点插入到结点*p*p 前面）前面） LNode *q;/LNode *q;/定义定义 q q 来寻找来寻找 p p 的前驱的前驱 whilewhile（q q- -next!=pnext!=p） q=qq=q- -next;next; S=(LNode *)malloc(sizeof(LNode);S=(LNode *)malloc(sizeof(LNode); S S- -next=qnext=q- -next;next; q q- -next=S;next=S; 题型五题型五：单链表删除单链表删除结点结点 void Delete_LinkList(LinkList L,int i) /删除第i个结点 LNode *p;/设第i个结点为p LNode *q; int j=0; while (q-next!=NULL j+; if (j!=i) printf(第%d-1个结点不存在,i-1); else if (q-next=NULL) printf(第%d个结点不存在,i); else p=q-next; q-next=p-next; free(p);/删除结点 题型六题型六：单链表的倒置单链表的倒置 void reverse_LinkList(LinkList L) LNode *p,*q; p=L-next; L-next=NULL; while(p!=NULL) q=p; p=p-next; q-next=L-next; L-next=q; 题型七题型七：有序单链表的合并有序单链表的合并 LinkList merge(LinkList A,LinkList B) /单链表A、B中的元素递增有序得到递减有序的单链表C LinkList C; LNode *p,*q,*s; p=A-next; q=B-next; C=A; C-next=NULL; free(B); while (p!=NU