單鏈表各種操作詳解

#include "stdio.h"
#include "stdlib.h"#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0#define MAXSIZE 20 /* 存儲空間初始分配量 */typedef int Status;/* Status是函數的類型,其值是函數結果狀態代碼，如OK等 */
typedef int ElemType;/* ElemType類型根據實際情況而定，這里假設為int */typedef struct Node
{ElemType data;struct Node *next;
}Node;
/* 定義LinkList */
typedef struct Node *LinkList;/* 初始化順序線性表 */
Status InitList(LinkList *L)
{*L=(LinkList)malloc(sizeof(Node)); /* 產生頭結點,并使L指向此頭結點 */if(!(*L)) /* 存儲分配失敗 */{return ERROR;}(*L)->next=NULL; /* 指針域為空 */return OK;
}/* 初始條件：順序線性表L已存在。操作結果：返回L中數據元素個數 */
int ListLength(LinkList L)
{int i=0;LinkList p=L->next; /* p指向第一個結點 */while(p){i++;p=p->next;}return i;
}/* 初始條件：順序線性表L已存在。操作結果：將L重置為空表 */
Status ClearList(LinkList *L)
{LinkList p,q;p=(*L)->next;           /*  p指向第一個結點 */while(p)                /*  沒到表尾 */{q=p->next;free(p);p=q;}(*L)->next=NULL;        /* 頭結點指針域為空 */return OK;
}/* 初始條件：順序線性表L已存在 */
/* 操作結果：依次對L的每個數據元素輸出 */
Status ListTraverse(LinkList L)
{LinkList p=L->next;while(p){visit(p->data);p=p->next;}printf("\n");return OK;
}/* 初始條件：順序線性表L已存在 */
/* 操作結果：依次對L的每個數據元素輸出 */
Status ListTraverseLimit(LinkList L, int n)
{int i = 0;LinkList p=L->next;while(p && i < n){visit(p->data);p=p->next;i++;}printf("\n只顯示 %d 個\n", n);return OK;
}Status visit(ElemType c)
{printf("-> %d ",c);return OK;
}/* 初始條件：順序線性表L已存在，1≤i≤ListLength(L) */
/* 操作結果：用e返回L中第i個數據元素的值 */
Status GetElem(LinkList L,int i,ElemType *e)
{int j;LinkList p;		/* 聲明一結點p */p = L->next;		/* 讓p指向鏈表L的第一個結點 */j = 1;		/*  j為計數器 */while (p && j < i)  /* p不為空或者計數器j還沒有等于i時，循環繼續 */{p = p->next;  /* 讓p指向下一個結點 */++j;}if ( !p || j>i )return ERROR;  /*  第i個元素不存在 */*e = p->data;   /*  取第i個元素的數據 */return OK;
}/* 初始條件：順序線性表L已存在 */
/* 操作結果：返回L中第1個與e滿足關系的數據元素的位序。 */
/* 若這樣的數據元素不存在，則返回值為0 */
int LocateElem(LinkList L,ElemType e)
{int i=0;LinkList p=L->next;while(p){i++;if(p->data==e) /* 找到這樣的數據元素 */return i;p=p->next;}return 0;
}/*  隨機產生n個元素的值，建立帶表頭結點的單鏈線性表L（頭插法） */
void CreateListHead(LinkList *L, int n)
{LinkList p;int i;srand(time(0));                         /* 初始化隨機數種子 */*L = (LinkList)malloc(sizeof(Node));(*L)->next = NULL;                      /*  先建立一個帶頭結點的單鏈表 */for (i=0; i < n; i++){p = (LinkList)malloc(sizeof(Node)); /*  生成新結點 */p->data = rand()%100+1;             /*  隨機生成100以內的數字 */p->next = (*L)->next;(*L)->next = p;						/*  插入到表頭 */}
}/*  隨機產生n個元素的值，建立帶表頭結點的單鏈線性表L（尾插法） */
void CreateListTail(LinkList *L, int n)
{LinkList p,r;int i;srand(time(0));                      /* 初始化隨機數種子 */*L = (LinkList)malloc(sizeof(Node)); /* L為整個線性表 */r=*L;                                /* r為指向尾部的結點 */for (i=0; i < n; i++){p = (Node *)malloc(sizeof(Node)); /*  生成新結點 */p->data = rand()%100+1;           /*  隨機生成100以內的數字 */r->next=p;                        /* 將表尾終端結點的指針指向新結點 */r = p;                            /* 將當前的新結點定義為表尾終端結點 */}r->next = NULL;                       /* 表示當前鏈表結束 */
}/* 初始條件：順序線性表L已存在,1≤i≤ListLength(L)， */
/* 操作結果：在L中第i個位置之前插入新的數據元素e，L的長度加1 */
Status ListInsert(LinkList *L,int i,ElemType e)
{int j;LinkList p,s;p = *L;     /* 聲明一個結點 p，指向頭結點 */j = 1;while (p && j < i)     /* 尋找第i個結點 */{p = p->next;++j;}if (!p || j > i)return ERROR;   /* 第i個元素不存在 */s = (LinkList)malloc(sizeof(Node));  /*  生成新結點(C語言標準函數) */s->data = e;s->next = p->next;      /* 將p的后繼結點賦值給s的后繼  */p->next = s;          /* 將s賦值給p的后繼 */return OK;
}/* 初始條件：順序線性表L已存在，1≤i≤ListLength(L) */
/* 操作結果：刪除L的第i個數據元素，并用e返回其值，L的長度減1 */
Status ListDelete(LinkList *L,int i,ElemType *e)
{int j;LinkList p,q;p = *L;j = 1;while (p->next && j < i)	/* 遍歷尋找第i個元素 */{p = p->next;++j;}if (!(p->next) || j > i)return ERROR;           /* 第i個元素不存在 */q = p->next;p->next = q->next;			/* 將q的后繼賦值給p的后繼 */*e = q->data;               /* 將q結點中的數據給e */free(q);                    /* 讓系統回收此結點，釋放內存 */return OK;
}/* 單鏈表反轉/逆序 */
LinkList ListReverse(LinkList L)
{LinkList current,pnext,prev;if(L == NULL || L->next == NULL)return L;current = L->next;  /* p1指向鏈表頭節點的下一個節點 */pnext = current->next;current->next = NULL;while(pnext){prev = pnext->next;pnext->next = current;current = pnext;pnext = prev;}//printf("current = %d,next = %d \n",current->data,current->next->data);L->next = current;  /* 將鏈表頭節點指向p1 */return L;
}LinkList ListReverse2(LinkList L)
{LinkList current, p;if (L == NULL){return NULL;}current = L->next;while (current->next != NULL){p = current->next;current->next = p->next;p->next = L->next;L->next = p;ListTraverse(L);printf("current = %d, \n", current -> data);}return L;
}LinkList ListReverse3(LinkList L)
{LinkList newList;    //新鏈表的頭結點LinkList tmp;       //指向L的第一個結點，也就是要摘除的結點//參數為空或者內存分配失敗則返回NULLif (L == NULL || (newList = (LinkList)malloc(sizeof(Node))) == NULL){return ERROR;}//初始化newListnewList->data = L->data;newList->next = NULL;//依次將L的第一個結點放到newList的第一個結點位置while (L->next != NULL){tmp = newList->next;         //保存newList中的后續結點newList->next = L->next;       //將L的第一個結點放到newList中L->next = L->next->next;     //從L中摘除這個結點newList->next->next = tmp;        //恢復newList中后續結點的指針}//原頭結點應該釋放掉，并返回新頭結點的指針free(L);return newList;
}// 獲取單鏈表倒數第N個結點值
Status GetNthNodeFromBack(LinkList L, int n, ElemType *e)
{int i = 0;LinkList firstNode = L;while (i < n && firstNode->next != NULL){//正數N個節點，firstNode指向正的第N個節點i++;firstNode = firstNode->next;printf("%d\n", i);}if (firstNode->next == NULL && i < n - 1){//當節點數量少于N個時，返回NULLprintf("超出鏈表長度\n");return ERROR;}LinkList secNode = L;while (firstNode != NULL){//查找倒數第N個元素secNode = secNode->next;firstNode = firstNode->next;//printf("secNode:%d\n", secNode->data);//printf("firstNode:%d\n", firstNode->data);}*e = secNode->data;return OK;
}// 找到鏈表的中間節點
Status GetMidNode(LinkList L, ElemType *e) {LinkList search, mid;mid = search = L;while (search->next != NULL){//search移動的速度是 mid 的2倍if (search->next->next != NULL){search = search->next->next;mid = mid->next;//printf("search %d\n", search->data);//printf("mid %d\n", mid->data);}else{search = search->next;}}*e = mid->data;return OK;
}int HasLoop(LinkList L)
{int step1 = 1;int step2 = 2;LinkList p = L;LinkList q = L;//while (p != NULL && q != NULL && q->next == NULL)while (p != NULL && q != NULL && q->next != NULL){p = p->next;if (q->next != NULL)q = q->next->next;printf("p:%d, q:%d \n", p->data, q->data);if (p == q)return 1;}return 0;
}int HasLoop2(LinkList L)
{int step1 = 1;int step2 = 2;LinkList p = L;LinkList q = L;while (p != NULL && q != NULL && q->next != NULL){p = p->next;if (q->next != NULL)q = q->next->next;printf("p:%d, q:%d \n", p->data, q->data);if (p == q)return 1;}return 0;
}Status BulidListLoop(LinkList *L, int num)
{int i = 0;LinkList cur = *L;LinkList tail = NULL;if(num <= 0 || L == NULL){return ERROR;}for(i = 1; i < num; ++i){if(cur == NULL){return ERROR;}cur = cur->next;}tail = cur;while(tail->next){tail = tail->next;}tail->next = cur;return OK;
}LinkList RemoveDupNode(LinkList L)//刪除重復結點的算法
{LinkList p,q,r;p=L->next;while(p)    // p用于遍歷鏈表{q=p;while(q->next) // q遍歷p后面的結點，并與p數值比較{if(q->next->data==p->data){r=q->next; // r保存需要刪掉的結點q->next=r->next;   // 需要刪掉的結點的前后結點相接free(r);}elseq=q->next;}p=p->next;}return L;
}int main()
{LinkList L;Status i;int j,k,pos,value;int opp;ElemType e;i=InitList(&L);printf("鏈表L初始化完畢，ListLength(L)=%d\n",ListLength(L));printf("\n1.整表創建（頭插法） \n2.整表創建（尾插法） \n3.遍歷操作 \n4.插入操作");printf("\n5.刪除操作 \n6.獲取結點數據 \n7.查找某個數是否在鏈表中 \n8.置空鏈表");printf("\n9.鏈表反轉逆序 \n10.求鏈表倒數第N個數 \n11.找到鏈表的中間結點 \n12.判斷鏈表是否有環");printf("\n13.鏈表建環 ");printf("\n14.鏈表去重 ");printf("\n0.退出 \n請選擇你的操作：\n");while(opp != '0'){scanf("%d",&opp);switch(opp){case 1:CreateListHead(&L,10);printf("整體創建L的元素(頭插法)：\n");ListTraverse(L);printf("\n");break;case 2:CreateListTail(&L,10);printf("整體創建L的元素(尾插法)：\n");ListTraverse(L);printf("\n");break;case 3:ListTraverse(L);printf("\n");break;case 4:printf("要在第幾個位置插入元素？");scanf("%d",&pos);printf("插入的元素值是多少？");scanf("%d",&value);ListInsert(&L,pos,value);ListTraverse(L);printf("\n");break;case 5:printf("要刪除第幾個元素？");scanf("%d",&pos);ListDelete(&L,pos,&e);printf("刪除第%d個元素成功，現在鏈表為：\n", pos);ListTraverse(L);printf("\n");break;case 6:printf("你需要獲取第幾個元素？");scanf("%d",&pos);GetElem(L,pos,&e);printf("第%d個元素的值為：%d\n", pos, e);printf("\n");break;case 7:printf("輸入你需要查找的數：");scanf("%d",&pos);k=LocateElem(L,pos);if(k)printf("第%d個元素的值為%d\n",k,pos);elseprintf("沒有值為%d的元素\n",pos);printf("\n");break;case 8:i=ClearList(&L);printf("\n清空L后：ListLength(L)=%d\n",ListLength(L));ListTraverse(L);printf("\n");break;case 9:ListReverse2(L);//L=ListReverse3(L);printf("\n反轉L后\n");ListTraverse(L);printf("\n");break;case 10:printf("你要查找倒數第幾個結點的值？");scanf("%d", &value);GetNthNodeFromBack(L,value,&e);printf("倒數第%d個元素的值為：%d\n", value, e);printf("\n");break;case 11:GetMidNode(L, &e);printf("鏈表中間結點的值為：%d\n", e);printf("\n");break;case 12:if( HasLoop(L) ){printf("方法一: 鏈表有環\n");}else{printf("方法一: 鏈表無環\n");}if( HasLoop2(L) ){printf("方法二: 鏈表有環\n");}else{printf("方法二: 鏈表無環\n");}printf("\n");break;case 13:printf("你要在哪個位置開始建環？");scanf("%d", &pos);BulidListLoop(&L, pos);ListTraverseLimit(L, 20);printf("\n");break;case 14:RemoveDupNode(L);ListTraverse(L);printf("\n");break;case 0:exit(0);}}}

延伸閱讀

此文章所在專題列表如下：

  1. 第01話：線性表的概念與定義
  2. 第02話：線性表的抽象數據類型ADT定義
  3. 第03話：線性表的順序存儲結構
  4. 第04話：線性表的初始化
  5. 第05話：線性表的遍歷、插入操作
  6. 第06話：判斷線性表是否為空與置空操作
  7. 第07話：線性表的查找操作
  8. 第08話：線性表刪除某個元素
  9. 線性表順序存儲的優缺點
  10. 線性表鏈式存儲結構的由來與基本概念
  11. 單鏈表的頭指針、頭結點與首元結點
  12. 單鏈表的結構體定義與聲明
  13. 單鏈表的初始化
  14. 單鏈表的插入與遍歷操作
  15. 單鏈表的刪除某個元素的操作
  16. 獲取單鏈表中的指定位置的元素
  17. 查找某數在單鏈表中的位置
  18. 用頭插法實現單鏈表整表創建
  19. 用尾插法實現單鏈表整表創建
  20. 將單鏈表重置為空表
  21. 單鏈表反轉/逆序的兩種方法
  22. 單鏈表反轉/逆序的第三種方法
  23. 求單鏈表倒數第N個數
  24. 用標尺法快速找到單鏈表的中間結點
  25. 如何判斷鏈表是否有環的存在
  26. 單鏈表建環，無環鏈表變有環
  27. 刪除單鏈表中的重復元素


本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/383697.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/383697.shtml
英文地址，請注明出處：http://en.pswp.cn/news/383697.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

Linux系統【五】進程間通信-共享內存mmap

Linux系統【五】進程間通信-共享內存mmap

mmap函數 #include <sys/mman.h> void *mmap(void *addr, size_t length, int prot, int flags,int fd, off_t offset);參數&#xff1a; void *addr建立映射區的首地址&#xff0c;由Linux內核指定&#xff0c;所以我們直接傳遞NULL。也就是說雖然這是一個參宿但是并不…
閱讀更多...
socket編程 -- epoll模型服務端/客戶端通信的實現

socket編程 -- epoll模型服務端/客戶端通信的實現

https://blog.csdn.net/y396397735/article/details/50680359 本例實現如下功能&#xff1a; 支持多客戶端與一個服務端進行通信&#xff0c;客戶端給服務端發送字符串數據&#xff0c;服務端將字符串中小寫轉為大寫后發送回客戶端&#xff0c;客戶端打印輸出經轉換后的字符串。…
閱讀更多...
Python3 面向對象程序設計

Python3 面向對象程序設計

類的定義 Python使用class關鍵字來定義類 class Car:def infor(self):print("This is a car") car Car() car.infor()內置方法isinstance()來測試一個對象是否為某個類的實例 self參數 類的 所有實例方法都有一個默認的self參數&#xff0c;并且必須是方法的第一…
閱讀更多...
計算機網絡【二】物理層基礎知識

計算機網絡【二】物理層基礎知識

計算機網絡的性能 速率&#xff1a;連接在計算機網絡上的主機在數字信道上傳送數據位數的速率&#xff0c;也成為data rate 或bit rate&#xff0c;單位是b/s,kb/s,Mb/s,Gb/s。 我們平時所講的寬帶的速度是以字為單位的&#xff0c;但是實際中應用一般顯示的是字節 &#xff0…
閱讀更多...
Linux網絡編程——tcp并發服務器（多進程）

Linux網絡編程——tcp并發服務器（多進程）

https://blog.csdn.net/lianghe_work/article/details/46503895一、tcp并發服務器概述一個好的服務器,一般都是并發服務器&#xff08;同一時刻可以響應多個客戶端的請求&#xff09;。并發服務器設計技術一般有&#xff1a;多進程服務器、多線程服務器、I/O復用服務器等。二、…
閱讀更多...
求序列第K大算法總結

求序列第K大算法總結

參考博客&#xff1a;傳送門 在上面的博客中介紹了求序列第K大的幾種算法&#xff0c;感覺收益良多&#xff0c;其中最精巧的還是利用快速排序的思想O(n)查詢的算法。仔細學習以后我將其中的幾個實現了一下。 解法 1&#xff1a; 將亂序數組從大到小進行排序然后取出前K大&a…
閱讀更多...
Linux網絡編程——tcp并發服務器（多線程）

Linux網絡編程——tcp并發服務器（多線程）

https://blog.csdn.net/lianghe_work/article/details/46504243tcp多線程并發服務器多線程服務器是對多進程服務器的改進&#xff0c;由于多進程服務器在創建進程時要消耗較大的系統資源&#xff0c;所以用線程來取代進程&#xff0c;這樣服務處理程序可以較快的創建。據統計&a…
閱讀更多...
計算機網絡【三】物理層數據通信

計算機網絡【三】物理層數據通信

物理層傳輸媒介 導向傳輸媒體&#xff0c;比如光纖和銅線 雙絞線&#xff08;屏蔽雙絞線STP 五屏蔽雙絞線UTP&#xff09;電線扭曲在一起可以降低互相之間的電磁干擾 同軸電纜 (50歐姆的基帶同軸電纜&#xff0c;75歐姆的寬帶同軸電纜) 10M和100M網絡只使用了四根線&#xf…
閱讀更多...
02_算法分析

02_算法分析

02_算法分析 0.1 算法的時間復雜度分析0.1.1 函數漸近增長概念&#xff1a;輸入規模n>2時&#xff0c;算法A1的漸近增長小于算法B1 的漸近增長隨著輸入規模的增大&#xff0c;算法的常數操作可以忽略不計測試二&#xff1a;隨著輸入規模的增大&#xff0c;與最高次項相乘的常…
閱讀更多...
Linux網絡編程——I/O復用之select詳解

Linux網絡編程——I/O復用之select詳解

https://blog.csdn.net/lianghe_work/article/details/46506143一、I/O復用概述I/O復用概念&#xff1a;解決進程或線程阻塞到某個 I/O 系統調用而出現的技術&#xff0c;使進程不阻塞于某個特定的 I/O 系統調I/O復用使用的場合&#xff1a;1.當客戶處理多個描述符&#xff08;…
閱讀更多...
Linux多進程拷貝文件

Linux多進程拷貝文件

學習了mmap以后&#xff0c;實現一個簡單的小程序&#xff0c;進行多個進程對一個文件進行拷貝。 Linux　mmap共享內存學習可以參考我的另一篇博客&#xff1a;傳送門 實現思想 我們可以將原來的文件利用mmap分成多個段分別進行傳輸。 實現代碼 #include<stdio.h> #…
閱讀更多...
斐波那契查找(Fibonacci Search)和折半查找

斐波那契查找(Fibonacci Search)和折半查找

兩個查找算法都是針對有序數組進行查找&#xff0c;不同點在于分界點的取值不同。 算法介紹 折半查找很簡單&#xff0c;每次與當前區間的中點進行比較&#xff0c;然后決定查找前一部分還是后一部分。 Fibonacci查找利用了Fibonacci序列每一項等于前兩項和的特點進行劃分&a…
閱讀更多...
Linux網絡編程——tcp并發服務器（I/O復用之select）

Linux網絡編程——tcp并發服務器（I/O復用之select）

https://blog.csdn.net/lianghe_work/article/details/46519633與多線程、多進程相比&#xff0c;I/O復用最大的優勢是系統開銷小&#xff0c;系統不需要建立新的進程或者線程&#xff0c;也不必維護這些線程和進程。代碼示例&#xff1a;#include <stdio.h> #include &l…
閱讀更多...
SQL server 2008下載+安裝詳細

SQL server 2008下載+安裝詳細

教程博客&#xff1a;傳送門
閱讀更多...
操作系統【二】死鎖問題以及處理方法

操作系統【二】死鎖問題以及處理方法

死鎖的概念 死鎖&#xff1a;在并發環境下&#xff0c;個進程因為競爭資源而造成的一種互相等待對方手里的資源&#xff0c;導致各進程都阻塞&#xff0c;無法向前推進的現象。 區別&#xff1a; 饑餓&#xff1a;由于長期得不到想要的資源進程無法向前推進的現象。死循環&a…
閱讀更多...
Linux網絡編程——I/O復用之poll函數

Linux網絡編程——I/O復用之poll函數

https://blog.csdn.net/lianghe_work/article/details/46534029一、回顧前面的selectselect優點&#xff1a;目前幾乎在所有的平臺上支持&#xff0c;其良好跨平臺支持也是它的一個優點select缺點&#xff1a;1.每次調用 select()&#xff0c;都需要把 fd 集合從用戶態拷貝到內…
閱讀更多...
操作系統【一】進程同步和信號量

操作系統【一】進程同步和信號量

基本概念 進程異步性特征&#xff1a;各并發執行的進程以各自獨立的&#xff0c;不可預知的速度向前推進。 進程同步又稱作直接制約關系&#xff0c;他是指為完成某種任務而建立的兩個或者多個進程&#xff0c;這些進程因為需要在某些位置上協調他們的工作順序而產生的制約關…
閱讀更多...
計算機網絡【四】數據鏈路層基本概念+點到點通信(PPP協議）

計算機網絡【四】數據鏈路層基本概念+點到點通信(PPP協議）

數據鏈路層基本概念 路由器是網絡層設備 數據鏈路層&#xff1a;數據管道&#xff0c;傳輸的是數據包加上發送地址&#xff0c;接收地址&#xff0c;校驗的數據幀 數據鏈路層的信道類型&#xff1a; 點到點信道&#xff1a;使用一對一的點到點通信方式&#xff08;兩個設備…
閱讀更多...
Linux網絡編程——tcp并發服務器（poll實現）

Linux網絡編程——tcp并發服務器（poll實現）

https://blog.csdn.net/lianghe_work/article/details/46535859想詳細徹底地了解poll或看懂下面的代碼請參考《Linux網絡編程——I/O復用之poll函數》 代碼&#xff1a;#include <string.h>#include <stdio.h>#include <stdlib.h>#include <unistd.h>#…
閱讀更多...
二分查找的最大比較次數

二分查找的最大比較次數

二分查找很簡單&#xff0c;可是對于一個區間長度為n的數組&#xff0c;最大的比較次數為多少呢&#xff1f; 對于標準的二分查找&#xff0c;我們每次從區間[l,r)中取一個值&#xff0c;和中間值mid(lr)>>1進行比較&#xff0c;然后將數組分為[l,mid) [mid1,r)&#xf…
閱讀更多...
最新文章

Copyright @ 2022~2023