單鏈表編程考點

1、將單鏈表的第一個結點放在單鏈表的最后一個結點的后面

/* 設h是無頭結點的單鏈表，如果線性表h的長度不小于2，則將首元結點刪除并插入到表尾 將單鏈表的第一個結點放在單鏈表的最后一個結點的后面 */ typedef struct node {elementype data;struct node *next; }*linklist;void change(linklist &h) //linklist &h等價于struct node *&h,這樣就可以修改指針h的值；此時不需要return返回已經修改的單鏈表的值 {linklist p,q; //linklist p,q等價于struct node *p、struct node *q；if(h && h->next) //如果鏈表中有不少于2個結點{q = h; //令p指向第1個結點hh = h->next; //令h指向第2個結點p = h; //令p指向第2個結點while(p->next) //第一次循環時，判斷第2個結點的指針域是否為空，如果為空則只有兩個結點，則不需要找到最后的一個結點，否則一直循環，找到最后一個結點為止p = p->next; //順著p開始往下找，一直找到最后一個結點p->next = q; //將第一個結點接在最后一個結點后面q->next = NULL; //新的尾結點沒有后繼，置后繼為空} } /*分析：1、在if判斷語句中h為單鏈表的某一指針指向單鏈表中的某一個結點2、q = h;此語句的含義是另外一個指針q與指針h同時指向同一個結點3、h = h->next;此語句中的h->next所表示的含義是h->next指向單鏈表中h指針指向的下一個結點，與此同時h指針和h->next指針同時指向該結點 */

?

typedef struct node {elementype data;struct node *next; }*Linklist;Linklist mynode(LinkList L) //L是不帶頭結點的單鏈表的頭指針 {if(L && L->next) //如果鏈表中有不少于2個結點{q = L; //令p指向第1個結點hL = L->next; //令h指向第2個結點p = L; //令p指向第2個結點while(p->next)p = p->next; //順著p開始往下找，一直找到最后一個結點p->next = q; //將第一個結點接在最后一個結點后面q->next = NULL; //新的尾結點沒有后繼，置后繼為空}return L; }

?

2、實現單鏈表的刪除算法,刪除成功返回1，刪除失敗返回0

/*實現單鏈表的刪除算法,刪除成功返回1，刪除失敗返回0*/ typedef struct node {elementype data;struct node *next; }*LinkList, LNode;int ListDelete(LinkList L, int i, ElemType *s) //s是存儲將要刪除的值，i是將要被刪除元素的指定位置 {LNode *p,*q; //定義了兩個新的指針變量p、q;int j;p = L; //p指向L單鏈表的第一個結點元素j = 0;while((p->next != NULL)&&(j < i-1)) //j < i-1此處的判斷條件是i-1的原因是當最后一次，不滿足條件之前，j的值自動增加了一位{p = p->next; //而我們進行刪除操作的前提是找到被刪除結點元素的前驅結點j++; }if(p->next == NULL || j > i-1)return 0; //如果if語句成立，將執行return 0;語句，運行過程終止q=p->next; //否則將q指針指向p->next指針所指的結點，即指向被刪除結點元素 *s = q->data;p->next = q->next; //此語句將指定位置的結點刪除，p->next所代表的是被刪結點元素的前驅結點的next指針域，而q->next指向被刪結點元素的后繼結點free(q); //釋放結點占有的存儲空間return 1; }

?

3、尾插法建立單鏈表

//尾插法建立單鏈表 typedef struct node {int data;struct node *next; }lklist; void lklistcreate(lklist *&head ,int n) //n表示單鏈表的長度 {lklist *q; //定義一個新的結點指針 for(i = 1;i<=n;i++){ p=(lklist *)malloc(sizeof(lklist)); //創建一個新的結點scanf("%d",&(p->data)); //獲取該結點的數值p->next = NULL;if(i==1)head = q = p; //head = q = p;該語句表示頭指針head，新的結點指針q都指向結點p;else{q->next = p; //注意：定義的新的結點指針q的作用是通過移動該指針的指向，來實現鏈表的創建,將q結點的next指針域指向最新創建的結點q=p; //將結點連接以后，再改變q指針的指向，為下一次新結點的創建作好準備}} }

　　

4、逆轉線性單鏈表，采用是頭插法

//逆轉線性單鏈表，采用是頭插法 typedef struct node //就地逆置單鏈表 {elemtype data;struct node *next; }node; node *Reverse (node *head) //head是帶頭結點的單鏈表 {node *p ,*q;p = head->next; //p指向第一個元素head->next=NULL; //保留第一個元素，將頭結點的指針域置空while(p!=NULL) //將原鏈表的元素用頭插法插入新的鏈表中{q=p; //令q指向鏈表的當前第一個元素p=p->next; //p指針后移q->next = head->next; //在新表中插入結點qhead->next = q;}return head; }

　　

5、在帶頭結點的單鏈表L中，刪除所有值為x的結點

//在帶頭結點的單鏈表L中，刪除所有值為x的結點 typedef struct LNode {Elemtype data;struct LNode *next; }LNode, *Linklist; void delete(Linklist &L ,ElemType x) {LNode *q=L;LNode p=L->next; //初始化p指向第一個結點，q始終指向p結點的前驅while(p!=NULL){if(p->data == x) //若p指針指向當前結點的值等于x{q->next = p->next;free(p); //刪除該結點，并修改p指針p=q->next; //尋找鏈表中下一個值為x的結點}else{q=p;p=p->next; //先使q后移，p向后移動}} }

　　

6、有序遞增序列，刪除所有值大于mink且小于maxk的元素

//有序遞增序列，刪除所有值大于mink且小于maxk的元素 typedef struct node //就地逆置單鏈表 {elemtype data;struct node *next; }node; void Delete_Between(node *head, int mink, int maxk) {node *p = head, *q;while(p->next->data <= mink) //p是最后一個不大于mink的元素p=p->next;if(p->next) //如果還有比mink更大的元素{q=p->next;while(q->data<maxk) //q是第一個不小于maxk的元素q=q->next; //while循環結束以后，q指向比maxk值還大的結點元素p->next = q; //此語句是刪除所有值大于mink且小于maxk的元素 } }

　　

7、將帶頭結點單鏈表h1和h2合并成升序排列的單鏈表

//將帶頭結點單鏈表h1和h2合并成升序排列的單鏈表 typedef struct L {int data;struct L *next; }LinkL; LinkL *mergeList(LinkL *h1, LinkL *h2) {LinkL *h, *Next, *q;h=h1;Next = h;h1=h1->next; //表h1的第一個結點h2=h2->next; //表h2的第一個結點while(h1 != NULL && h2 != NULL) //如果表h1和h2均不為空表{if(h1->data <= h2->data) //如果h1指針所指向當前結點的值小于h2{ //指針所指向的當前結點的值q=h1; //則令q暫存h1指針所指向的結點h1=h1->next; //h1指針向后移動}else //如果h2指針所指向當前結點的值小于h1{ //指針所指向的當前結點的值q=h2; //則令q暫存h2指針所指向的結點h2-h2->next; //h2指針向后移動}Next->next = q; //將指針p所指向的結點接在Next指針所指的結點后面Next = q; }if(h1 == NULL) //如果原h2鏈表中所有結點已插入但是原h1鏈表還有結點沒插完，則直接把剩余部分接在next指針后面。要是原h1表的所有結點已經全部插完但是h2還有結點沒插完，亦是如此Next->next = h2;if(h2 == NULL)Next->next = h1;return h; //返回新表的指針}

　　

8、用單鏈表lc表示集合C,分別將la中的元素取出，再在lb中進行查找，如果在lb中出現，則將其插入到lc中

//將單鏈表A分解成一個小于零的單鏈表和大于零的單鏈表 typedef struct node {elemtype data;struct node *next; }*LinkList,Linknode; void decompose（LinkList La,LinkList Lb,LinkList Lc） {Linknode *p; Lc=(Linknode *)malloc(sizeof(Linknode)); Lc->next = NULL; //表C的頭結點的next域置空p=La->next; //令p指向表A的第一個元素結點Lb=La; //令Lb指向表LaLb->next = NULL; //令表La的next域置空while(p) //遍歷原表A{La=p->next; //令La暫存p結點的后繼指針if(p->data >0) //如果p結點值大于0，則接在表C后面{p->next=Lc->next;Lc->next = p;}else{ //如果p結點的值小于0，則接在表B后面p->next =Lb->next;Lb->next = p;}p=La; //令p指向原p所指向的結點的下一個位置} }

　　

9、將單鏈表A分解成一個小于零的單鏈表和大于零的單鏈表

//用單鏈表lc表示集合C,分別將la中的元素取出，再在lb中進行查找，如果在lb中出現，則將其插入到lc中 typedef struct node {elemtype data;struct node *next; }*LinkList,LNode; void interaction(LinkList la, LinkList lb, LinkList &lc) {LinkList pa ,pb, pc;lc = new LNode(); //生成lc的頭結點pc=lc; //pc永遠指向lc的尾結點pa=la->next; //pa指向la的第一個元素while(pa){pb=lb->next; //pa指向lb表的第一個元素while(pb && pb->data != pa->data)pb=pb->next; //在pb中查找元素，使其值等于pa->dataif(pb) //如果存在這樣的元素{pc->next = new LNode(); //生成lc新的尾結點pc = pc->next; //pc指向新的尾結點pc->data= pa->data; //將pa->data復制到pc中}pa=pa->next; //繼續比較pa表的下一個結點元素}pc->next =NULL; //pc為尾結點，pc表比較完成后，置pc后繼為空 }

　　

10、已知指針hb和ha分別指向兩個單鏈表的頭結點，長度為m和n，假設hc指向連接后的鏈表的頭結點

//已知指針hb和ha分別指向兩個單鏈表的頭結點，長度為m和n，假設hc指向連接后的鏈表的頭結點 typedef struct node {elemtype data;struct node *next; }LinkList; void ListConcat(LinkList ha, LinkList hb, LinkList *hc) { LinkList p; //把鏈表hb接在ha后面形成鏈表hchc=ha; //由指針p指向ha的尾元結點while(p->next !=NULL) //查找原ha表的最后一個結點p=p->next;p->next = hb->next; //把hb表的第一個元素及其后面元素接在p指針指向的結點后面free(hb); }

　　

11、刪除單鏈表中重復的元素

//刪除單鏈表中重復的元素 typedef struct node {elemtype data;struct node *next; }LinkedList ,*LNode; LinkedList DeleteSameElement(LinkedList L) { //L為遞增有序的單鏈表LNode u;LinkedList p, pre;pre = L->next; //pre指針指向第一個元素結點p= pre->next; //p指向pre所指結點的后繼結點while(p!=NULL) //如果p指針不為空if(p->data == pre->data) //p所指結點的值等于pre所指結點的值{u=p; //用指針u暫存p指針所指向的結點p=p->next; //p指針后移free(u); //釋放掉u指針所值結點的內存空間}else{ //p和pre兩指針所指向的結點值不相等pre = p; //pre指針后移p = p->next; //p指針后移} }

　　

12、交換單鏈表中指針p所指結點與其后繼結點

//交換單鏈表中指針p所指結點與其后繼結點 typedef struct node {elemtype data;struct node *next; }*LinkList; int exchange(Linklist &head,Linklist p ) {LinkList q=head->next; //q指向第一個元素結點LinkList pre=head; //pre指向頭結點while(q!=NULL && q!=p) //順著鏈表開始查找，一直到q=p{pre=q;q=q->next;}if(p->next ==NULL) //退出循環之后，若p無后繼，則交換失敗return 0;else{q=p->next;pre->next = q;p->next = q->next;q->next = p;}return 1; }

　　

13、設有一個無序單鏈表
　　1）找出最小值結點
　　2）若該數是奇數將與其直接后繼結點的數值交換
　　3）該數值是偶數將直接后繼結點刪除

/* 設有一個無序單鏈表 1、找出最小值結點 2、若該數是奇數將與其直接后繼結點的數值交換 3、該數值是偶數將直接后繼結點刪除 */ typedef struct node {elemtype data;struct node *next; }LinkList; void OutputMin(LinkList L) {int temp;LinkList q = L->next; //p指向第一個元素結點LinkList p= q;while(q){ //找出最小值結點p，并打印p結點數值if(p->data >q->data)p=q; //如果發現還有比p指針所指結點的值更小的結點，令p指向該結點，否則q后移q=q->next;}printf("%d",p->data);if(p->next != NULL) //找到了值最小的結點，若該結點有后繼結點{if(p->data % 2 == 1) //如果該最小值是奇數，則與其后繼結點交換{temp=p->data;p->data =p->next->data;p->next->data = temp;}else //如果該最小值是偶數，則刪除其后繼結點{q=p->next;p->next = q->next;free(q);}} }

　　

　　

轉載于:https://www.cnblogs.com/wxt19941024/p/7460528.html

總結

以上是生活随笔為你收集整理的08、单链表编程考点的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。