（含有頭結(jié)點(diǎn)以及尾結(jié)點(diǎn)）單鏈表各類功能的實(shí)現(xiàn)
來源：程序員人生 發(fā)布時(shí)間：2015-06-08 09:00:59 閱讀次數(shù)：2733次
對(duì)單鏈表實(shí)現(xiàn)以下功能：
void InitList(List *list); //初始化單鏈表
bool push_back(List *list,ElemType x); //尾插法
void show_seqlist(List *list); //顯示鏈表內(nèi)容
bool push_front(List *list,ElemType x);//頭插法
bool pop_back(List *list); //尾刪法
bool pop_front(List *list); //頭刪法
Node *find(List *list,ElemType x); //查找函數(shù)，找到返回指向該元素的指針
bool modify(List *list,ElemType x); //修改某1元素的值
void delete_val(List *list,ElemType x);//按值刪除
void clear(List *list); //清空鏈表
void destroy(List *list); //燒毀鏈表
int length(List *list); //求鏈表長(zhǎng)度
void resver(List *list); //逆至鏈表
void prio(List *list,ElemType x); //求某個(gè)值的先驅(qū)
void next(List *list,ElemType x); //求某個(gè)值的后繼
List.h:
#ifndef __LIST_H__
#define __LIST_H__
#include<assert.h>
#include<iostream>
using namespace std;
typedef int ElemType;
typedef struct Node
{
ElemType data;
struct Node *next;
}Node;
typedef struct List
{
Node *first;
Node *last;
int size;
}List;
void InitList(List *list); //初始化單鏈表
bool push_back(List *list,ElemType x); //尾插法
void show_seqlist(List *list); //顯示鏈表內(nèi)容
bool push_front(List *list,ElemType x);//頭插法
bool pop_back(List *list); //尾刪法
bool pop_front(List *list); //頭刪法
Node *find(List *list,ElemType x); //查找函數(shù)，找到返回指向該元素的指針
bool modify(List *list,ElemType x); //修改某1元素的值
void delete_val(List *list,ElemType x);//按值刪除
void clear(List *list); //清空鏈表
void destroy(List *list); //燒毀鏈表
int length(List *list); //求鏈表長(zhǎng)度
void resver(List *list); //逆至鏈表
void prio(List *list,ElemType x); //求某個(gè)值的先驅(qū)
void next(List *list,ElemType x); //求某個(gè)值的后繼
#endif
List.cpp:
#include"List.h"
//初始化單鏈表
void InitList(List *list)
{
Node *s = (Node *)malloc(sizeof(Node));
assert(s != NULL);
s->next = NULL;
list->first = list->last = s;
list->size = 0;
}
//尾插法：開辟并初始化--->>連接---->>指針后移
bool push_back(List *list,ElemType x)
{
Node *s = (Node *)malloc(sizeof(Node));//開辟1個(gè)結(jié)點(diǎn)
if(s == NULL)
{
return false;
}
s->next = NULL;//對(duì)節(jié)點(diǎn)的初始化
s->data = x;
list->last->next = s;//連接
list->last = s; //后移（尾指針后移）
list->size++;
return true;
}
//打印鏈表的內(nèi)容
void show_seqlist(List *list)
{
Node *p = list->first->next;
while(p != NULL)
{
cout<<p->data<<"--->";
p = p->next;
}
cout<<"NULL"<<endl;
}
//頭插法：開辟并初始化--->>連接---->>指針后移 ！！注意特殊情況！！
bool push_front(List *list,ElemType x)
{
Node *s = (Node *)malloc(sizeof(Node));
if(s == NULL)
{
return false;
}
s->data = x;
s->next = list->first->next;
list->first->next = s;
//注意：如果是第1個(gè)結(jié)點(diǎn)，則尾指針需要改變指向即指向第1個(gè)結(jié)點(diǎn)
//（不再指向頭）如果不是第1個(gè)結(jié)點(diǎn)，尾指針指向無需改變
if(list->size == 0)
{
list->last = s;
}
list->size++;
return true;
}
//尾刪法：找到最后1個(gè)節(jié)點(diǎn)的先驅(qū)（指向賦空）---->尾指針指向它--->size - 1
bool pop_back(List *list)
{
if(list->size == 0)
{
cout<<"鏈表已空"<<endl;
return false;
}
Node *pre = list->first;
while(pre->next != list->last)//找到要?jiǎng)h除節(jié)點(diǎn)（最后1個(gè)結(jié)點(diǎn)）的先驅(qū)
{
pre = pre->next;
}
pre->next = NULL;//由于該先驅(qū)要作為尾結(jié)點(diǎn)，所以其指針域得賦空
free(list->last);//釋放要?jiǎng)h除的結(jié)點(diǎn)
list->last = pre;//尾指針指向改變
/* pre->next = NULL;
list->last = pre;
free(pre);
pre = NULL;
// free(list->last);*/
list->size--;
return true;
}
//free(p)作用是：釋放p所指向的空間，而非釋放指針p！！！！！
//動(dòng)態(tài)開辟的空間才需要手工釋放，其他的空間系統(tǒng)自動(dòng)回收
//頭刪法：釋放第1個(gè)節(jié)點(diǎn)->size⑴(如果只有1個(gè)節(jié)點(diǎn)，釋放它以后尾指針得指向頭結(jié)點(diǎn))，其他情況尾指針不變
bool pop_front(List *list)
{
if(list->size == 0)
{
cout<<"鏈表已空"<<endl;
return false;
}
Node *p = list->first->next;//p指向要釋放的第1個(gè)節(jié)點(diǎn)
list->first->next = p->next;//頭指針指向下1個(gè)節(jié)點(diǎn)
free(p); //釋放第1個(gè)節(jié)點(diǎn)
if(list->size == 1)
{
list->last = list->first;//如果只有1個(gè)節(jié)點(diǎn)，釋放它以后尾指針得指向頭結(jié)點(diǎn))，其他情況尾指針不變
}
list->size--;
return true;
}
//查找函數(shù)
/*Node *find(List *list,ElemType x)
{
Node *p = list->first->next;//p指向第1個(gè)節(jié)點(diǎn)
while(p != NULL)
{
if(x == p->data)
return p;
else
p = p->next;
}
return NULL;
}*/
Node *find(List *list,ElemType x)
{
Node *p = list->first->next;//p指向第1個(gè)節(jié)點(diǎn)
while(p!=NULL && p->data!= x)
{
p = p->next;
}
return p;//while循環(huán)退出條件：沒找到則-->p=NULL,找到p為指向所尋覓節(jié)點(diǎn)的指針
}
//修改函數(shù)
bool modify(List *list,ElemType x)
{
ElemType item;
Node *p = find(list,x);
if(p != NULL)
{
cout<<"Please input the new value:"<<endl;
cin>>item;
p->data = item;
cout<<"it is modified"<<endl;
return true;
}
else
cout<<"it's not exist!"<<endl;
}
//按值刪除結(jié)點(diǎn)
void delete_val(List *list,ElemType x)
{
Node *p = find(list,x); //找到要?jiǎng)h除的結(jié)點(diǎn)
if(p != NULL)
{
if(p == list->first->next)//如果是第1個(gè)結(jié)點(diǎn)（頭刪法）
{
pop_front(list);
}
else if(p == list->last) //如果是最后1個(gè)結(jié)點(diǎn)（尾刪法）
{
pop_back(list);
}
else //既不是第1個(gè)結(jié)點(diǎn)，也不是最后1個(gè)節(jié)點(diǎn)
{
p->data = p->next->data;//將要?jiǎng)h除的結(jié)點(diǎn)的data賦值為下1個(gè)節(jié)點(diǎn)的data
p->next = p->next->next;//連接
free(p->next); //將要?jiǎng)h除的結(jié)點(diǎn)的下1個(gè)結(jié)點(diǎn)釋放
}
/*else //既不是第1個(gè)結(jié)點(diǎn)，也不是最后1個(gè)節(jié)點(diǎn)
{
Node *pre = list->first;
while(pre->next != p)//找到要?jiǎng)h除節(jié)點(diǎn)的先驅(qū)
{
pre = pre->next;
}
pre->next = p->next;//連接
free(p); //釋放要?jiǎng)h除的結(jié)點(diǎn)
}*/
list->size--;
cout<<"it is deleted!"<<endl;
}
else
{
cout<<"it is not exist!"<<endl;
}
}
//清空單鏈表
/*void clear(List *list,ElemType x)
{
for(int i=0;i<list->size;++i)
{
pop_back(list);//或pop_front(list)
}
}*/
void clear(List *list)
{
Node *p = list->first->next;//p指向第1個(gè)節(jié)點(diǎn)
while(p != NULL)
{
list->first->next = p->next;//分離出第1個(gè)結(jié)點(diǎn)
free(p);//將第1個(gè)節(jié)點(diǎn)釋放
p = list->first->next;//又指向第1個(gè)節(jié)點(diǎn)(連續(xù)刪除第1個(gè)結(jié)點(diǎn))
}
list->last = list->first; //尾指針和頭指針都指向頭結(jié)點(diǎn)
list->size = 0;
}
//燒毀鏈表
void destroy(List *list)
{
clear(list);//清空鏈表
free(list->first);//頭結(jié)點(diǎn)釋放
list->first = list->last = NULL;//頭（尾）指針賦空，避免成為野指針
}
//求鏈表長(zhǎng)度
int length(List *list)
{
return list->size;
}
//鏈表逆至
/*改變指針的指向*/
void resver(List *list)
{
Node *pre = list->first->next;//pre指向第1個(gè)節(jié)點(diǎn)
Node *p = pre->next; // p指向第2個(gè)結(jié)點(diǎn)
pre->next = NULL; //逆序以后第1個(gè)節(jié)點(diǎn)成為最后1個(gè)節(jié)點(diǎn)，所以next=NULL
while(p != NULL)
{
Node *pre1 = pre;//將當(dāng)前的指向保存下來
Node *p1 = p;
pre = p; //為下1次（第n⑴次）交換做準(zhǔn)備（必須在指向改變以后進(jìn)行！！！！！）
p = p->next;
p1->next = pre1;//交換當(dāng)前兩個(gè)(第n次)后1個(gè)指向前1個(gè)
}
list->first->next = pre; //退出循環(huán)，p=NULL,pre指向原來的最后1個(gè)結(jié)點(diǎn)（逆序后成為第1個(gè)）
}
/*交換值*/
/*void resver(List *list)
{
Node *left = list->first->next;
Node *right = list->last;
Node *p = list->first;
while(left != right)
{
left->data = left->data + right->data;//對(duì)稱的兩個(gè)數(shù)交換
right->data = left->data - right->data;
left->data = left->data - right->data;
while(p->next != right)//找到倒數(shù)第2個(gè)結(jié)點(diǎn)
{
p = p->next;
}
right = p;//為下1次交換做準(zhǔn)備
left = left->next;
}
}*/
//求某個(gè)值的先驅(qū)
void prio(List *list,ElemType x)
{
Node *p = find(list,x);
if(p == NULL)
{
cout<<"it is not exist!
"<<endl;
}
if(p == list->first->next)
{
cout<<"it does not have next"<<endl;
}
else
{
Node *pre = list->first;
while(pre->next != p)
{
pre = pre->next;
}
cout<<"it's prio is found"<<endl;
cout<<"it is"<<pre->data<<endl;;
}
}
//求某個(gè)值的后繼
void next(List *list,ElemType x)
{
Node *p = find(list,x);
if(p == NULL)
{
cout<<"it is not exist!
"<<endl;
}
if(p == list->last)
{
cout<<"it does not have next"<<endl;
}
else
{
cout<<"it's next is found"<<endl;
cout<<"it is"<<p->next->data<<endl;
}
}
main.cpp:
#include"List.h"
void main()
{
List mylist;
InitList(&mylist);
int select = 1;
ElemType item;
Node *p = NULL;
while(select)
{
cout<<"**********************************"<<endl;
cout<<"* [1] push_back [2] push_front *"<<endl;
cout<<"* [3] show_seqlist[0] quit_system*"<<endl;
cout<<"* [4] pop_back [5] pop_front *"<<endl;
cout<<"* [6] find *"<<endl;
cout<<"* [7] modify [8] clear *"<<endl;
cout<<"* [9] destroy [10]delete_val *"<<endl;
cout<<"* [11] resver [12]length *"<<endl;
cout<<"* [13] prio [14]next *"<<endl;
cout<<"**********************************"<<endl;
cout<<"請(qǐng)選擇:>";
cin>>select;
switch(select)
{
case 1:
cout<<"請(qǐng)輸入要插入的數(shù)據(jù)(⑴結(jié)束):>";
while(cin>>item,item!=⑴)
{
push_back(&mylist,item);
}
break;
case 2:
cout<<"請(qǐng)輸入要插入的數(shù)據(jù)(⑴結(jié)束):>";
while(cin>>item,item!=⑴)
{
push_front(&mylist,item);
}
break;
case 3:
show_seqlist(&mylist);
break;
case 4:
pop_back(&mylist);
break;
case 5:
pop_front(&mylist);
break;
case 6:
cout<<"輸入你要查找的值：";
cin>>item;
p =find(&mylist,item);
if(p != NULL)
cout<<"it is found!"<<endl;
else
cout<<"it is not exit!"<<endl;
break;
case 7:
cout<<"請(qǐng)輸入要修改的值：";
cin>>item;
modify(&mylist,item);
break;
case 8:
clear(&mylist);
break;
case 9:
destroy(&mylist);
break;
case 10:
cout<<"請(qǐng)輸入要?jiǎng)h除的值：";
cin>>item;
delete_val(&mylist,item);
break;
case 11:
resver(&mylist);
break;
case 12:
{
int n = length(&mylist);
cout<<"the length of the list is:"<<n<<endl;
}
break;
case 13:
cout<<"輸入你要查找先驅(qū)的值：";
cin>>item;
prio(&mylist,item);
break;
case 14:
cout<<"輸入你要查找后繼的值：";
cin>>item;
next(&mylist,item);
break;
default:
break;
}
}
destroy(&mylist);//函數(shù)調(diào)用完以后，自動(dòng)燒毀鏈表
}
生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對(duì)您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)
