数据结构-线性表

线性表的链式表示与基本操作

1.初始化

初始化带头结点的单链表

1
2
3
4
5
6
7
8
9
10
11
12
13
int InitLinkList(LinkList &L)
{
L=(LinkList)malloc(sizeof(LNode));//为头结点分配空间
if(L!=NULL)
{
L->next=NULL;//初始化next指针为NULL
return OK;
}
else
{
return ERROR;//分配空间失败,返回ERROR
}
}

2.采用头插法建立单链表

特点:每次在头结点后插入新结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
LinkList CreatList1(LinkList &L){
LNode *node;int x=0;
if(!L)
InitLinkList(L);
scanf("%d",&x);
while(x!=9999){
node=(LNode *)malloc(sizeof(LNode));
node->data=x;
node->next=L->next;
L->next=node;
scanf("%d",&x);
}
return L;
}

3.采用尾插法建立单链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
LinkList CreatList2(LinkList &L){
LNode *node;int x;LNode *r=L;
if(!L)
InitLinkList(L);
scanf("%d",&x);
while(x!=9999){
node=(LNode *)malloc(sizeof(LNode));
node->data=x;
r->next=node;
r=node;
scanf("%d",&x);
}
r->next=NULL;
return L;
}

4.按序号查找结点值

从第一个结点出发,顺着next指针逐个往后搜索,直到找到第i个结点,返回该结点,若不存在,则返回NULL

1
2
3
4
5
6
7
8
9
10
11
12
13
LinkList GetElem(LinkList L,int i){
int j=1;//j为计数变量
LNode *p=L->next;
if(i==0)
return L;//若i==0,返回头结点
if(i<1)
return NULL;//i值无效,返回NULL
while(p&&j<i){
p=p->next;
j++;
}
return p;
}

5.按值查找结点值

从第一个结点出发,顺着next指针逐个往后搜索,直到找到结点值等于e的结点,返回该结点,若不存在,则返回NULL

1
2
3
4
5
6
7
LinkList LocateElem(LinkList L,ElemType e){
LNode *p=L->next;
while(p&&p->data!=e){
p=p->next;
}
return p;
}

6.插入结点操作

目标:将值为x的新结点插入到单链表的第i个位置上

1
2
3
4
5
6
7
8
LinkList insertforlist(LinkList &L,int x,int i){
LNode *p=GetElem(L,i-1);LNode *node;//调用GetElem函数
node=(LNode *)malloc(sizeof(LNode));
node->data=x;
node->next=p->next;
p->next=node;
return node;
}

7.删除结点操作

目标:将单链表的第i个位置上结点删除

1
2
3
4
5
6
LinkList DeleteElem(LinkList &L,int i){
LNode * p=GetElem(L,i-1);LNode *q;
q=p->next;
p->next=q->next;
free(q);
}

8.求单链表长度

目标:统计单链表的长度(即包含多少节点)

1
2
3
4
5
6
7
8
9
10
int ListLength_L(LinkList L){
//返回L中数据元素个数
LNode *p;int i=0;
p=L->next;//p指向第一个结点,因为不包含头结点
while(p){//遍历单链表,统计节点数
i++;
p=p->next;
}
return i;
}

未完待续。。


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!