C語言數據結構之單鏈表的查找和建立

Posted on by

單鏈表的查找

其實在單鏈表的插入和刪除中，我們已經使用過單鏈表的查找方法，因為插入和刪除的前提都是先找到對應的結點，所以這裡就不再多解釋

按位查找

GetElem(L, i)：按位查找操作。獲取表 L 中第 i 個位置的元素的值

//按位查找
LNode * GetElem(LinkList L, int i) {
	if (i < 0) return false;

	LNode *p;		//指針p指向當前掃描到的結點
	int j = 0;		//當前p指向的是第幾個結點
	p = L;			//L指向頭結點，頭結點是第 0 個結點

	//循環找到第 i-1 個結點
	while (p != NULL && j < i) {
		p = p->next;
		j++;
	}
	return p;
}

按值查找

LocateElem(L, e)：按值查找操作。在表 L 中查找具有給定關鍵字值的元素

//按值查找
LNode * LocateElem(LinkList L, ElemType e) {
    LNode *p = L->next;
    //從第1個結點開始查找數據域為e的結點
    while (p && p->data != e) {
        p = p->next;
    }
    return p;

單鏈表的建立

如果給你很多個數據元素（ElemType），要把它們存到一個單鏈表裡面，怎麼操作呢？

第一步：初始化一個單鏈表

第二步：每次取一個數據元素，插入到表尾/表頭

尾插法

算法步驟：

1.創建一個隻有頭結點的空鏈表

2.尾指針 r 初始化，指向頭結點

3.接收用戶輸入的值，判斷是否結束插入，不結束則插入表中

  • 創建新結點 *s
  • 將用戶輸入的值賦給新節點 *s 的數據域
  • 將新節點 *s 插入到尾結點 *r 之後
  • 尾指針 r 指向新的尾結點 *s
  • 用戶繼續輸入
//尾插法建立單鏈表
LinkList List_TailInsert(LinkList &L) {
    int x;        //假設ElemType為整型        
    L = (LinkList)malloc(sizeof(LNode));    //建立頭結點
    LNode *s, *r = L;        //r為表尾指針
    scanf("%d", &x);        //輸入結點的值
    while (x != 9999) {        //輸入9999表示結束
        s = (LNode *)malloc(sizeof(LNode));
        s->data = x;
        r->next = s;
        r = s;                //r指向新的表尾結點
        scanf("%d", &x);
    }
    r->next = NULL;        //尾結點指針置空
    return L;
}

頭插法建立單鏈表

算法步驟：

1.創建一個隻有頭結點的空鏈表

2.接收用戶輸入的值，判斷是否結束插入，不結束則插入表中

  • 創建新結點 *s
  • 將用戶輸入的值賦給新節點 *s 的數據域
  • 將新節點 *s 插入到頭結點之後
  • 用戶繼續輸入
//頭插法建立單鏈表
LinkList List_HeadInsert(LinkList &L) {
    LNode *s;
    int x;        //假設ElemType為整型        
    L = (LinkList)malloc(sizeof(LNode));    //建立頭結點
    L->next = NULL;
    scanf("%d", &x);        //輸入結點的值
    while (x != 9999) {        //輸入9999表示結束
        s = (LNode *)malloc(sizeof(LNode));
        s->data = x;
        s->next = L->next;
        L->next = s;
        scanf("%d", &x);
    }
    return L;
}

記得 L->next = NULL; 這一句不能漏瞭，不然會出問題

到此這篇關於C語言數據結構之單鏈表的查找和建立的文章就介紹到這瞭,更多相關C語言單鏈表內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：