数据结构--单链表

1.单链表的定义：

单链表基本操作的实现：

2.单链表的初始化（构造带头结点的空表）

2.将头结点的指针域置空

3.链表是否为空：

4.单链表的销毁：

5.单链表的清空:

6.求单链表的表长：

7. 取值取单链表第i个元素：

8按值查找根据指定数据查找指定数据所在位置序号（地址）

9.插入操作在第i个结点前插入元素为e的新结点

10.删除结点：删除第i个元素

11.头插法元素插入在链表头部

表示空表：

1.无头结点：头指针的指针域为空

2.有头结点：头节点的指针域为空

1.单链表的定义：

typedef struct Lnode{int data;struct Lnode *next;}Lnode,*LinkList;

首先定义struct Londe结构体，结构体内有data ，指向该结构体的指针next

再用typedef 将该结构体命名为Lnode类型，*LinkList为指向Lnode结构体的指针类型

定义链表（头指针）：LinkList L；//L即为指针

定义结点指针：Lnode *p；

单链表基本操作的实现：

2.单链表的初始化（构造带头结点的空表）

算法步骤：

1.生成新结点作头结点，用头指针L指向头结点

2.将头结点的指针域置空

int InitList(LinkList &L){L = new Lnode;L->next=NULL;return 1;}

3.链表是否为空：

空表：链表中无元素，称为空链表（头指针和头结点仍然在）

int ListEmpty(LinkList L)
{if(L->next)cout<<"空表"<<endl;return 0;
elsereturn 1;
}

4.单链表的销毁：

算法思路：从头指针开始，依次释放所有结点

int DestoryList(LinkList &L){Lnode *p;while(L){  p=L;L=L->next;delete p;}
return OK;
}

5.单链表的清空:

int ClearList(LinkList &L)

{

Lnode *p,* q;

p=L->next;

q=p->next;

delete p;

while(p!=NULL)

{

q=p;

q=q->next;

delete p;

}

L->next=NULL;
}

int ClearList(LinkList &L)
{Lnode *p,*q;p=L->next;while(p){q=p->next;delete p;q=p;}L->next=NULL;return ok;}

6.求单链表的表长：

算法思路：从首元结点开始，依次计数所有结点

int ListLength(LinkList L)
{   Lnode *p;p = L->next;int i=0;while(p){p=p->next;i++;} return i;
}

7. 取值取单链表第i个元素：

算法步骤：从第一个结点顺链扫描，用指针p指向当前扫描到的结点，p初值p=L->next

j作计数器，累计当前扫描过得结点数，j初值为1

当p指向扫描到的下一结点时，计数器j加1

当j==i时，p所指的结点就是要找的第i个结点

int GetElem(LinkList L,int i,int &e)
{Lnode *p;p=L->next;int j=1; while(p&&j>i){//向后扫描，直到P指向第i个元素或p为空P=P->next;++j;}if(!p||j>i) return ERROR;e=p->data;return OK;
}

8按值查找根据指定数据查找指定数据所在位置序号（地址）

int FindElem(LinkList L,int e){Lnode *p;p=L->next;int i=1;while(p&&p->data!=e){p=p->next;i++;}return i;if(p) return i;else return 0;
}

Lnode *LocateElem(LinkList L,int e){
//在线性表中查找值为e的数据元素
//找到，则返回L中值为e的数据元素地址，查找失败返回NULLp=p->next;while(p&&p->data!=e){p=p->next;}return p;
}

9.插入操作在第i个结点前插入元素为e的新结点

算法步骤：1.首先找到ai-1的存储位置p

2生成一个数据域为e的新节点s

3插入新结点:1新结点的指针域指向结点ai

2.结点ai-1的指针域指向新结点

int InsertElem(LinkList &L,int i,int e)
{Lnode *p,*s;L = p;int j=0;while(p!=NULL&&j<i-1) {p=p->next;++j;}if(p==NULL||j>i-1) return ERROR;s -> data = e ;s -> next = p ->next;p -> next = s;return OK;}

10.删除结点：删除第i个元素

int DeleteElem(LinkList &L,int i,int &e){Lnode *p,*q;int j=0;while(p->next&&j<i-1){p=p->next;++j;}if(!(p->next)||j>i-1)q=p->next;p->next=q->next;e=q->data;//将要删除元素用e保存，要用时可以用delete q;return OK;
}

11.头插法元素插入在链表头部

int CreatList(LinkList &L,int n){L = new Lnode;L->next=NULL;//建立一个带头结点的单链表for(int i=n;i>0;--i){p = new Lnode;//生成新结点cin>>p->data;//输入插入的元素p->next=L->next;//将新结点插到表头p=L->next;//在将新结点与头结点连接}
}