【数据结构】链表定义及其常用的基本操作（C/C++）

---

 目录

●图示 

●链表类型定义

●常用的基本操作（单链表）

●简单案例

---

●图示 

---

  ●链表类型定义

1.单链表存储结构的定义

typedef struct lnode{elemtype data;struct lnode *next;
}lnode,*linklist; 

定义链表L：linklist &L；

定义结点指针：lnode *p;

实例如下：

        ①数据和链表结构的第一种定义方法

typedef struct student{char num[8];char name[8];int score;struct student *next;
}lnode,*linklist;

        ②将数据和链表结构第二种定义方法

typedef struct{char num[8];char name[8];int score;
}elemtype;
typedef struct lnode{elemtype date;struct lnode *next;
}lnode,*linklist;

2. 带尾指针循环链表的合并（将单链表的头尾用指针进行相连）

linklist connect(linklist ta,linklist tb)
{p=ta->next;ta->next=tb->next->next;delete tb->next;tb->next=p;return tb;	
} 

3.双向链表结构的定义

typedef struct lnode{elemtype data;struct lnode *prior,*next;	
}lnode,*linklist;

---

●常用的基本操作（单链表）

1.链表的初始化

void initlist(linklist &L)
{L = new lnode;L->next = NULL;
}

2. 判断链表是否为空

int listempty(linklist& L)
{if (L->next)return 0;elsereturn 1;
}

3. 单链表的销毁

int destorylist(linklist& L)
{lnode* p;while (L != NULL){p = L;L = L->next;delete p;}return 1;
}

4. 单链表的清空

int clearlist(linklist& L)
{lnode* p;  //结点指针lnode* q;p = L->next;while (p){q = p->next;delete p;p = q;}L->next = NULL;return 1;
}

5. 求链表表长

int listlength(linklist& L)
{lnode* p;p = L->next;int i = 0;while (p){i++;p = p->next;}return 1;
}

6. 取单链表中第i个元素的内容 

int getelem(linklist& L, int i, elemtype e)
{lnode* p;p = L->next;int j = 1;while (p && j < i){p = p->next;j++;}if (!p || j > i){return 0;}e = p->data;return 1;
}

7. 在第i个结点前插入值为e的新结点

int listinsert(linklist& L, int i, elemtype e)
{lnode* p;p = L;int j = 0;while (p && j < i - 1){p = p->next;j++;}if (!p || j > i - 1){return 0;}linklist s;s = new lnode;s->data = e;s -> next = p -> next;p -> next = s;return 1;
}

8. 删除第i个结点

int listdelete(linklist& L, int i, elemtype e)
{lnode* p;lnode* q;p = L;int j = 0;while (p->next&&j<i-1){p = p->next;j++;}if (!(p->next) || j > i - 1){return 0;}q = p->next;p->next = q->next;e = q->data;delete q;return 1;
}

9. 头插法

void createlist_H(linklist &L,int n)
{linklist p;for(i=n;i>0;i--){p=new lnode;cin>>p->date; //输入数据p->next=L->next;L->next=p;	} 
}

10.尾插法

void create_R(linklist &L,int n)
{linklist p;linklist r;r=L;while(i=0;i<n;i++){p=new lnode;	cin>>p->date;  //输入数据p->next=NULL; r->next=p;r=p;	}	
} 

---

●简单案例

（这里只实现用顺序表存储3个学生的学号、姓名、年龄并且将其输出查看。若进行其他操作，对代码进行简单修改即可）

#include<iostream>
using namespace std;
//数据的准备
typedef struct {char key[10];char name[20];int age;
}elemtype;
typedef struct lnode {elemtype data;struct lnode* next;
}lnode,*linklist;
//链表的初始化
void initlist(linklist &L)
{L = new lnode;L->next = NULL;
}
//判断链表是否为空
int listempty(linklist& L)
{if (L->next)return 0;elsereturn 1;
}
//单链表的销毁
int destorylist(linklist& L)
{lnode* p;while (L != NULL){p = L;L = L->next;delete p;}return 1;
}
//单链表的清空
int clearlist(linklist& L)
{lnode* p;  //结点指针lnode* q;p = L->next;while (p){q = p->next;delete p;p = q;}L->next = NULL;return 1;
}
//求链表表长
int listlength(linklist& L)
{lnode* p;p = L->next;int i = 0;while (p){i++;p = p->next;}return 1;
}
//取单链表中第i个元素的内容 
int getelem(linklist& L, int i, elemtype e)
{lnode* p;p = L->next;int j = 1;while (p && j < i){p = p->next;j++;}if (!p || j > i){return 0;}e = p->data;return 1;
}
//在第i个结点前插入值为e的新结点	
int listinsert_L(linklist& L, int i, elemtype e)
{lnode* p;p = L;int j = 0;while (p && j < i - 1){p = p->next;j++;}if (!p || j > i - 1){return 0;}linklist s;s = new lnode;s->data = e;s -> next = p -> next;p -> next = s;return 1;
}
//删除第i个结点
int listdelete(linklist& L, int i, elemtype e)
{lnode* p;lnode* q;p = L;int j = 0;while (p->next&&j<i-1){p = p->next;j++;}if (!(p->next) || j > i - 1){return 0;}q = p->next;p->next = q->next;e = q->data;delete q;return 1;
}
//头插法
void createlist_H(linklist& L, int n)
{linklist p;for (int i = n; i > 0; i--){p = new lnode;cin >> p->data.key;cin >> p->data.name;cin >> p->data.age;p->next = L->next;L->next = p;}
}
//尾插法
void create_R(linklist& L, int n)
{linklist p;linklist r;r = L;for(int i = 0; i < n; i++){p = new lnode;cin >> p->data.key;cin >> p->data.name;cin >> p->data.age;p->next = NULL;r->next = p;r = p;}
}
//查询所有结点
void listall(linklist& L,int n)
{lnode* p;p = L->next;for(int i=1;i<=n;i++){ cout << p->data.key << " "<<p->data.name <<" "<< p->data.age << endl;p=p->next;}
}
void showfunc()
{cout << "1.单链表的初始化" << endl;cout << "2.判断单链表是否为空" << endl;cout << "3.单链表的销毁" << endl;cout << "4.单链表的清空" << endl;cout << "5.求单链表表长" << endl;cout << "6.取单链表中第i个元素的内容" << endl;cout << "7.在第i个结点前插入值为e的新结点" << endl;cout << "8.删除第i个结点" << endl;cout << "9.头插法" << endl;cout << "10.尾插法" << endl;cout << "11.查询顺序表所有结点" << endl;
}
void text()
{linklist ll;while(1){ showfunc();cout << "#要执行的操作#" << endl;int n;cin >> n;switch (n){int num;case 1:initlist(ll);cout << "初始化成功" << endl;break;case 10:cout << "要输入的学生数：" << endl;cin >> num;createlist_H(ll, num);cout << "输入成功" << endl;break;case 11:listall(ll,num);break;}system("pause");system("cls");  //每执行一次操作清一次屏}
}
int main()
{text();
}

---