程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> C說話 數據構造之鏈表完成代碼

C說話 數據構造之鏈表完成代碼

編輯:關於C++

C說話 數據構造之鏈表完成代碼。本站提示廣大學習愛好者:(C說話 數據構造之鏈表完成代碼)文章只能為提供參考,不一定能成為您想要的結果。以下是C說話 數據構造之鏈表完成代碼正文


媒介

比來在溫習數據構造的相干常識,感到在初學的時刻照樣有許多器械沒有控制,不外如今終究算是弄得比擬有眉目了,所以就在寫出來和年夜家一路分享!

甚麼是鏈表

簡略的說,鏈表就是由多個結點團圓分派,彼此經由過程指針相連,每一個結點只要一個先驅結點和後繼結點。首節點無先驅結點,為結點無後繼結點的一種存儲構造。

鏈表的構造


頭結點:鏈表的第一個有用結點後面的結點,頭結點其實不寄存有用數據,也就是數據域為空,加頭結點的重要目標是為了便利鏈表的操作。

首節點:鏈表的第一個有用結點,結點包括數據域和指針域。

尾結點:尾結點的指針域為空。

頭指針:指向頭結點的指針變量,它寄存了頭結點的地址(在這裡留意一下,指針變量寄存的是地址,也就是說頭指針寄存的是

頭結點的地址,普通經由過程頭指針對鏈表停止操作)。

詳細完成

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
//界說鏈表節點
typedef struct Node
{
 int data;  //數據域
 struct Node * pNext; //指針域
}NODE, * PNODE;  //NODE等價於struct Node, PNODE等價於struct Node *
//函數聲明
PNODE createLinkList(void);    //創立鏈表的函數
void traverseLinkList(PNODE pHead);   //遍歷鏈表的函數
bool isEmpty(PNODE pHead);    //斷定鏈表能否為空的函數
int getLength(PNODE pHead);    //獲得鏈表長度的函數
bool insertElement(PNODE pHead, int pos, int val); //向鏈表中拔出元素的函數,三個參數順次為鏈表頭結點、要拔出元素的地位和要拔出元素的值
bool deleteElement(PNODE pHead, int pos, int * pVal); //從鏈表中刪除元素的函數,三個參數順次為鏈表頭結點、要刪除的元素的地位和刪除的元素的值
void sort(PNODE pHead);     //對鏈表中的元素停止排序的函數(基於冒泡排序)
int main(void)
{
 int val;   //用於保留刪除的元素
 PNODE pHead = NULL;  //PNODE等價於struct Node *
 pHead = createLinkList(); //創立一個非輪回單鏈表,並將該鏈表的頭結點地址賦給pHead
 traverseLinkList(pHead); //挪用遍歷鏈表的函數
 if(isEmpty(pHead))
 printf("鏈表為空!\n");
 else
 printf("鏈表不為空!\n");
 printf("鏈表的長度為:%d\n", getLength(pHead));
 //挪用冒泡排序函數
 sort(pHead);
 //從新遍歷
 traverseLinkList(pHead);
 //向鏈表中指定地位處拔出一個元素
 if(insertElement(pHead, 4, 30))
 printf("拔出勝利!拔出的元素為:%d\n", 30);
 else
 printf("拔出掉敗!\n");
 //從新遍歷鏈表
 traverseLinkList(pHead);
 //刪除元素測試
 if(deleteElement(pHead, 3, &val))
 printf("元素刪除勝利!刪除的元素是:%d\n", val);
 else
 printf("元素刪除掉敗!\n");
 traverseLinkList(pHead);
 system("pause");
 return 0;
}

PNODE createLinkList(void)
{
 int length; //有用結點的長度
 int i;
 int value; //用來寄存用戶輸出的結點的值
 //創立了一個不寄存有用數據的頭結點
 PNODE pHead = (PNODE)malloc(sizeof(NODE));
 if(NULL == pHead)
 {
 printf("內存分派掉敗,法式加入!\n");
 exit(-1);
 }
 PNODE pTail = pHead; //pTail一直指向尾結點
 pTail->pNext = NULL; //清空指針域
 printf("請輸出您想要創立鏈表結點的個數:len = ");
 scanf("%d", &length);
 for(i=0;i<length;i++)
 {
 printf("請輸出第%d個結點的值:", i+1);
 scanf("%d", &value);
 PNODE pNew = (PNODE)malloc(sizeof(NODE));
 if(NULL == pHead)
 {
  printf("內存分派掉敗,法式加入!\n");
  exit(-1);
 }
 pNew->data = value; //向新結點中放入值
 pTail->pNext = pNew; //將尾結點指向新結點
 pNew->pNext = NULL; //將新結點的指針域清空
 pTail = pNew;  //將新結點賦給pTail,使pTail一直指向為尾結點
 }
 return pHead;
}

void traverseLinkList(PNODE pHead)
{
 PNODE p = pHead->pNext;
 while(NULL != p)
 {
 printf("%d ", p->data);
 p = p->pNext;
 }
 printf("\n");
 return;
}

bool isEmpty(PNODE pHead)
{
 if(NULL == pHead->pNext)
 return true;
 else
 return false;
}

int getLength(PNODE pHead)
{
 PNODE p = pHead->pNext;  //指向首節點
 int len = 0;   //記載鏈表長度的變量
 while(NULL != p)
 {
 len++;
 p = p->pNext;  //p指向下一結點
 }
 return len;
}

void sort(PNODE pHead)
{
 int len = getLength(pHead); //獲得鏈表長度  
 int i, j, t;   //用於交流元素值的中央變量
 PNODE p, q;   //用於比擬的兩個中央指針變量
 for(i=0,p=pHead->pNext ; i<len-1 ; i++,p=p->pNext)
 {
 for(j=i+1,q=p->pNext;j<len;j++,q=q->pNext)
 {
  if(p->data > q->data)
  {
  t = p->data;
  p->data = q->data;
  q->data = t;
  }
 }
 }
 return;
}

bool insertElement(PNODE pHead, int pos, int val)
{
 int i = 0;
 PNODE p = pHead;
 //斷定p能否為空而且使p終究指向pos地位的結點
 while(NULL!=p && i<pos-1)
 {
 p = p->pNext;
 i++;
 }
 if(NULL==p || i>pos-1)
 return false;
 //創立一個新結點
 PNODE pNew = (PNODE)malloc(sizeof(NODE));
 if(NULL == pNew)
 {
 printf("內存分派掉敗,法式加入!\n");
 exit(-1);
 }
 pNew->data = val;
 //界說一個暫時結點,指向以後p的下一結點
 PNODE q = p->pNext;
 //將p指向新結點
 p->pNext = pNew;
 //將q指向之前p指向的結點
 pNew->pNext = q;
 return true;
}

bool deleteElement(PNODE pHead, int pos, int * pVal)
{
 int i = 0;
 PNODE p = pHead;
 //斷定p能否為空而且使p終究指向pos結點
 while(NULL!=p->pNext && i<pos-1)
 {
 p = p->pNext;
 i++;
 }
 if(NULL==p->pNext || i>pos-1)
 return false;
 //保留要刪除的結點
 * pVal = p->pNext->data;
 //刪除p前面的結點
 PNODE q = p->pNext;
 p->pNext = p->pNext->pNext;
 free(q);
 q = NULL;
 return true;
}

開頭語

下面完成的重要是單鏈表,別的還有雙鏈表、輪回鏈表、非輪回鏈表等其他幾種罕見鏈表。雙鏈表的特別性表示在每一個根本結點有兩個指針域;輪回鏈表的特征重要表示在,在輪回鏈表中,經由過程任何一個結點可以找到其他一切結點。

感謝年夜家的浏覽,願望能贊助到年夜家,感謝年夜家對本站的支撐!

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved