資料結構–單鏈表的c語言實作(超詳細注釋/實驗報告)
知識小回顧
在順序表中,用一組地址連續的存盤單元來一次存放線性表的結點,因此結點的邏輯順序和物理順序是一致的,而鏈表則不然,鏈表是用一組任意的存盤單元來存放線性表的結點,這組儲存單元可以是連續的,也可以是非連續的,甚至是零散分布在記憶體的任何位置上,因此鏈表中結點的邏輯順序和物理順序不一定相同,為了正確地表示結點間的邏輯關系,必須存盤線性表的每個資料元素值的同時,存盤知識其后繼結點的地址(位置)資訊,這兩部分資訊組成的存盤映像成為結點(Node),
實驗題目
實作單鏈表表各種基本運算
實驗目的
- 熟悉將演算法轉換為程式代碼的程序;
- 熟練掌握順序表的基本運算:頭插法建表、尾插法建表、按序號查找、按值查找、求表長度、插入元素、洗掉指定元素等,
實驗要求
- 以單鏈表表作為存盤結構;
- 實作單鏈表上的資料元素的頭插法建表、尾插法建表、按序號查找、按值查找、求表長度、插入元素、洗掉指定元素等操作,
實驗內容和實驗步驟
1)需求分析
以選單的形式作為用戶與程式的介面,用戶輸入選單號來實行相應的操作,
2)概要設計
設計幾個函式來實作初始化、頭插法建表、尾插法建表、按序號查找、按值查找、求表長度、插入元素和洗掉指定元素的功能,然后再主函式中呼叫函式來實作操作,
3)詳細設計
匯入相關的庫
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
單鏈表的存盤結構,
注意:LinkList 和 Node * 同為結構體指標型別,這兩種型別是等價的,
通常習慣上用LinkList說明指標變數,強調它是某個單鏈表的頭指標變數,
such as 使用定義LinkList L,則L為單鏈表的頭指標,從而提高程式的可讀性,
使用Node * 來定義只想單鏈表中節點的指標,例如,Node *p,則p為指向單鏈表中節點的指標變數,
typedef int ElemType;
typedef struct Node
{
ElemType data;
struct Node * next;
}Node,* LinkList;
/*LinkList 和 Node * 同為結構體指標型別,這兩種型別是等價的,
通常習慣上用LinkList說明指標變數,強調它是某個單鏈表的頭指標變數,
such as 使用定義LinkList L,則L為單鏈表的頭指標,從而提高程式的可讀性,
使用Node * 來定義只想單鏈表中節點的指標,例如,Node *p,則p為指向單鏈表中節點的指標變數,*/
初始化單鏈表
//初始化單鏈表
void Init_LinkList(LinkList *L)
{
*L=(LinkList)malloc(sizeof(Node));//建立頭結點
(*L)->next=NULL;//建立空的單鏈表
//注意:L是指向單鏈表頭結點的指標,用來接收主程式中帶初始化單鏈表的頭指標變數的地址,
//*L相當于主程式中帶初始化單鏈表的頭指標變數,
}
頭插法建表(逆序建表法)
演算法思想:從一個空表開始,每次讀入資料,生成新結點,將讀入資料存放到新結點的資料域中,然后將新節點插入到當前鏈表的表頭結點之后,直至讀入結束標志為止,
//用頭插法建立單鏈表
void CreateFromHead(LinkList L)
{
//L是帶頭結點的空鏈表頭指標,通過鍵盤輸入表中個元素值,利用頭插法建單鏈表L
Node *s;//s為只想單鏈表中結點的指標變數
char c;
int flag=1;
while(flag)
{
c=getchar();
if(c!='$')
{
s=(Node *)malloc(sizeof(Node));//建立新的結點
s->data=(int)c;//給s賦值
s->next=L->next;//把s變成頭結點的后一個,后面的話,新的s都是L的后一個,這樣也就導致了邏輯順序和輸入元素順序相反
L->next=s;
}
else flag=0;
}
}
尾插法建表(順序)
演算法思想:將新節點插到前單鏈表的表尾上,為此需要增加一個尾指標r,使之只想當前單鏈表的表尾,
//尾插法建表
void CreateFromTail(LinkList L)
{
Node *r,*s;//一個動態的尾指標r
int flag=1;
r=L;
char c;
while(flag)
{
c=getchar();
// printf(" ");
if(c!='$')
{
s=(Node*)malloc(sizeof(Node));
s->data=(int)c;
r->next=s;
r=s;//r始終是在最后的
}
else
{
flag=0;
r->next=NULL;//將最后一個結點的next鏈域設為空,表示鏈表的結束
}
}
}
按序號查找元素,
演算法思想:在單鏈表中,由于每個系欸但的存盤位置都放在其前一結點的next域中,所以即使知道被訪問結點的序號i,也不能像順序表那樣直接按序號i訪問以為陣列中的相應元素,實作隨機存取,而只能從來鏈表的頭指標出發,順鏈域next逐個結點往下搜索,直至搜索到第i個結點為止,
//在單鏈表L中查找第i個結點
Node* Get(LinkList L,int i)
{
int j;
Node *p;
if(i<0)
return NULL;
p=L;
j=0;//j是一個計數器,用來與i比較
while((p->next!=NULL)&&(j<i))//判斷條件為:到達表尾或等于要查找的結點
{
p=p->next;
j++;
}
if(i==j)
return p;
else
return NULL;
}
按值查找元素,
演算法思想:從單鏈表的頭指標指向的頭結點出發,順鏈逐個將結點值和給定值
e
e
e作比較,列印出查找結果,
//在單鏈表中查找值為x的結點
int Locate(LinkList L,int x)
{
LinkList p;
int j=1;
p=L->next;
while(p!=NULL&&p->data!=x)
{
p=p->next;
j++;
}
if(p)
{
printf("%d在鏈表中,是第%d個元素",p->data-48,j);//由于是ascii,所以-48
}
else
{
printf("該數值不在鏈表里,\n");
return 0;
}
}
求單鏈表的長度,
演算法思想:采用“數結點”的方法求出帶頭結點單鏈表的長度,即從“頭”開始“數”(p=l->next),用指標p依次指向各個結點,并附設計數器j技術,一直“數"到最后一個結點(p->next==NULL),從而得到單鏈表的長度,
//求單鏈表的長度
int ListLength(LinkList L)
{
Node *p;
p=L->next;
int j=0;//計數器j
while(p!=NULL)
{
p=p->next;
j++;
}
printf("%d",j);
return 0;
}
單鏈表插入操作,
演算法思想:
- 查找:在單鏈表中找到第i-1個結點,并由指標p表示,
- 申請:申請新結點s,將其數值域的值置為e,
- 插入:尾插法插入,
//單鏈表插入操作
int Insert_LinkList(LinkList L,int i,char x)
{
Node *p,*s;
p=Get(L,i-1);//這是一個小細節,如果設為i的話就不能實作在第1個元素前面插入的操作了
if(p==NULL)
{
printf("引數i輸入有誤!\n");
return 0;
}
else
{
//其實就是尾插法
s=(Node *)malloc(sizeof(Node));
s->data=x;
s->next=p->next;
p->next=s;
return 1;
}
}
單鏈表洗掉操作,
演算法思想:
- 查找:通過計數方式找到第i-1個基點,并由pre指示,
- 洗掉第i個結點并釋放空間,
//單鏈表洗掉操作
int Delete_LinkList(LinkList L,int i)
{
//在帶頭結點的單鏈表L中洗掉第i個元素
Node *pre,*r;
int k;
pre=L;k=0;
while(pre->next!=NULL&&k<i-1)
{
pre=pre->next;
k++;
}
if(pre->next==NULL)
{
printf("洗掉結點的位置i不合理!\n");
return 0;
}
r=pre->next;//r指向要洗掉的第i個結點
pre->next=r->next;//第i個結點前的結點的后一個結點變成第i個結點后一個結點
free(r);//釋放r
return 1;
}
顯示單鏈表,
演算法思想:順著指標一個一個地列印,
//display單鏈表
void Display_LinkList(LinkList L)
{
//printf("display呼叫開始\n");
Node *p;
ElemType s;
p=L;
while(p->next)
{
//p=p->next;
printf("%c ",p->next->data);//由于前面是getchar(),所以%c
//printf(" ");
p=p->next;
}
//printf("display呼叫結束\n");
}
主函式,用一種“選單”的形式使單鏈表的操作更加地清晰地展示出來,


int main()
{
LinkList L;
ElemType e,x;
int i=1,k,j;
Init_LinkList(&L);
printf("尾插法建立單鏈表如下:\n(輸入規則:一個數字一個數字地輸入,不用加空格和回車,空格和回車也會被當作是一個字符,結束的時候請輸入'$')\n");
CreateFromTail(&L);
system("cls");//清屏
while(i)//保證一直進行
{
printf("\n現在的鏈表: ");
Display_LinkList(&L);
printf("\n-------------------------------------\n");
printf(" Main Menu \n");
printf(" 1 在單鏈表中查找第i個結點 \n");
printf(" 2 在單鏈表中查找值為key的結點 \n");
printf(" 3 求單鏈表的長度 \n");
printf(" 4 單鏈表插入(在第i個結點插入e) \n");
printf(" 5 單鏈表洗掉操作 \n");
printf(" 6 清屏 \n");
printf(" 0 結束程式 \n");
printf("--------------------------------------\n");
printf("請輸入你選擇的選單號<1, 2, 3, 4, 5, 6, 0>:\n");
scanf("%d",&i);
switch(i)
{
case 1:
printf("請輸入要查找的結點:");
scanf("%d",&x);
Node *p1;
p1=Get(&L,x);
//printf("%d",p1->data-48);
printf(p1);
printf("\n");
break;
case 2:
printf("請輸入要查找的值x:");
scanf("%d",&x);
Locate(&L,x+48);
printf("\n\n");
break;
case 3:
printf("長度為");
//ListLength(&L);
int p3=ListLength(&L);
//printf(ListLength(&L));
//Display_LinkList(&L);
//printf("%d",p3);
printf("\n\n");
break;
case 4:
printf("要插入到哪個結點前?\n");
int i;
scanf("%d",&i);
//ElemType e;
int e;
printf("要插入哪個值呢?\n");
scanf("%s",&e);
Insert_LinkList(&L,i,e);
printf("\n\n");
break;
case 5:
printf("要洗掉到哪個結點呢?\n");
int ii;
scanf("%d",&ii);
ElemType ee;
Delete_LinkList(&L,ii);
//Display_LinkList(&L);
printf("\n\n");
break;
case 6:
system("cls");
break;
case 0:
exit(0);
break;
default:
printf("輸入有誤~");
}
}
return 0;
}
4)除錯分析
遇到的問題及解決方法
- 有很多細節需要好好琢磨和除錯
演算法的時空分析
- 都是比較基礎的操作,沒有涉及很復雜的演算法,故時空復雜度也還不算很大,
實驗結果
實驗結果很不錯,所有操作都能正常執行,并且自己加入了“清屏”選項,使得界面更加的整潔,
實驗總結
這是第二個資料結構的代碼實作,這一次就沒有直接照著實驗指導敲了,是結合教材和實驗指導以及同學的代碼寫出來的,這次寫完之后識訓很大!多多重復,百煉成鋼!
最后附上完整的代碼
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
//用typedef 給int定義個名字為ElemType,意思是表中元素的type
typedef int ElemType;
typedef struct Node
{
ElemType data;
struct Node * next;
}Node,* LinkList;
/*LinkList 和 Node * 同為結構體指標型別,這兩種型別是等價的
,通常習慣上用LinkList說明指標變數,強調它是某個單鏈表的頭
指標變數,such as 使用定義LinkList L,則L為單鏈表的頭指標,從而提高程式的可讀性,
使用Node * 來定義只想單鏈表中節點的指標,例如,Node *p,則p為指向單鏈表中節點的指標變數,*/
//初始化單鏈表
void Init_LinkList(LinkList *L)
{
*L=(LinkList)malloc(sizeof(Node));//建立頭結點
(*L)->next=NULL;//建立空的單鏈表
//注意:L是指向單鏈表頭結點的指標,用來接收主程式中帶初始化單鏈表的頭指標變數的地址,
//*L相當于主程式中帶初始化單鏈表的頭指標變數,
}
//用頭插法建立單鏈表
void CreateFromHead(LinkList L)
{
//L是帶頭結點的空鏈表頭指標,通過鍵盤輸入表中個元素值,利用頭插法建單鏈表L
Node *s;//s為只想單鏈表中結點的指標變數
char c;
int flag=1;
while(flag)
{
c=getchar();
if(c!='$')
{
s=(Node *)malloc(sizeof(Node));//建立新的結點
s->data=(int)c;//給s賦值
s->next=L->next;//把s變成頭結點的后一個,后面的話,新的s都是L的后一個,這樣也就導致了邏輯順序和輸入元素順序相反
L->next=s;
}
else flag=0;
}
}
//尾插法建表
void CreateFromTail(LinkList L)
{
Node *r,*s;//一個動態的尾指標r
int flag=1;
r=L;
char c;
while(flag)
{
c=getchar();
// printf(" ");
if(c!='$')
{
s=(Node*)malloc(sizeof(Node));
s->data=(int)c;
r->next=s;
r=s;//r始終是在最后的
}
else
{
flag=0;
r->next=NULL;//將最后一個結點的next鏈域設為空,表示鏈表的結束
}
}
}
//在單鏈表L中查找第i個結點
Node* Get(LinkList L,int i)
{
int j;
Node *p;
if(i<0)
return NULL;
p=L;
j=0;//j是一個計數器,用來與i比較
while((p->next!=NULL)&&(j<i))//判斷條件為:到達表尾或等于要查找的結點
{
p=p->next;
j++;
}
if(i==j)
return p;
else
return NULL;
}
//在單鏈表中查找值為x的結點
int Locate(LinkList L,int x)
{
LinkList p;
int j=1;
p=L->next;
while(p!=NULL&&p->data!=x)
{
p=p->next;
j++;
}
if(p)
{
printf("%d在鏈表中,是第%d個元素",p->data-48,j);//由于是ascii,所以-48
}
else
{
printf("該數值不在鏈表里,\n");
return 0;
}
}
//求單鏈表的長度
int ListLength(LinkList L)
{
Node *p;
p=L->next;
int j=0;//計數器j
while(p!=NULL)
{
p=p->next;
j++;
}
printf("%d",j);
return 0;
}
int Insert_LinkList(LinkList L,int i,char x)
{
Node *p,*s;
p=Get(L,i-1);//這是一個小細節,如果設為i的話就不能實作在第1個元素前面插入的操作了
if(p==NULL)
{
printf("引數i輸入有誤!\n");
return 0;
}
else
{
//其實就是尾插法
s=(Node *)malloc(sizeof(Node));
s->data=x;
s->next=p->next;
p->next=s;
return 1;
}
}
//單鏈表洗掉操作
int Delete_LinkList(LinkList L,int i)
{
//在帶頭結點的單鏈表L中洗掉第i個元素
Node *pre,*r;
int k;
pre=L;k=0;
while(pre->next!=NULL&&k<i-1)
{
pre=pre->next;
k++;
}
if(pre->next==NULL)
{
printf("洗掉結點的位置i不合理!\n");
return 0;
}
r=pre->next;
pre->next=r->next;
//e=r;
free(r);
return 1;
}
//display單鏈表
void Display_LinkList(LinkList L)
{
//printf("display呼叫開始\n");
Node *p;
ElemType s;
p=L;
while(p->next)
{
//p=p->next;
printf("%c ",p->next->data);
//printf(" ");
p=p->next;
}
//printf("display呼叫結束\n");
}
int main()
{
LinkList L;
ElemType e,x;
int i=1,k,j;
Init_LinkList(&L);
printf("尾插法建立單鏈表如下:\n(輸入規則:一個數字一個數字地輸入,不用加空格和回車,空格和回車也會被當作是一個字符,結束的時候請輸入'$')\n");
CreateFromTail(&L);
system("cls");
while(i)//保證一直進行
{
printf("\n現在的鏈表: ");
Display_LinkList(&L);
printf("\n-------------------------------------\n");
printf(" Main Menu \n");
printf(" 1 在單鏈表中查找第i個結點 \n");
printf(" 2 在單鏈表中查找值為key的結點 \n");
printf(" 3 求單鏈表的長度 \n");
printf(" 4 單鏈表插入(在第i個結點插入e) \n");
printf(" 5 單鏈表洗掉操作 \n");
printf(" 6 清屏 \n");
printf(" 0 結束程式 \n");
printf("--------------------------------------\n");
printf("請輸入你選擇的選單號<1, 2, 3, 4, 5, 6, 0>:\n");
scanf("%d",&i);
switch(i)
{
case 1:
printf("請輸入要查找的結點:");
scanf("%d",&x);
Node *p1;
p1=Get(&L,x);
//printf("%d",p1->data-48);
printf(p1);
printf("\n");
break;
case 2:
printf("請輸入要查找的值key:");
//char key;
scanf("%d",&x);
//Node *p2;
Locate(&L,x+48);
printf("\n\n");
break;
case 3:
printf("長度為");
//ListLength(&L);
int p3=ListLength(&L);
printf("\n\n");
break;
case 4:
printf("要插入到哪個結點前?\n");
int i;
scanf("%d",&i);
int e;
printf("要插入哪個值呢?\n");
scanf("%s",&e);
Insert_LinkList(&L,i,e);
printf("\n\n");
break;
case 5:
printf("要洗掉到哪個結點呢?\n");
int ii;
scanf("%d",&ii);
ElemType ee;
Delete_LinkList(&L,ii);
printf("\n\n");
break;
case 6:
system("cls");
break;
case 0:
exit(0);
break;
default:
printf("輸入有誤~");
}
}
return 0;
}
轉載請註明出處,本文鏈接:https://www.uj5u.com/qita/303042.html
標籤:其他
