数据结构链式表
数据结构链式表
1.线性表的链式存储实现
2.如何访问序号为i的元素？
3.如何求线性表的长度？
4.插入操作：
5.删除操作：（删除链表的第i（1<=i<=n）个位置上的结点）
（1）先找到链表的第i-1个结点，用p指向；
（2）再用指针s指向要被删除的结点（p的下一个节点）
（3）然后修改指针，删除s所指节点；
（4）释放s所指结点的空间；
#include <stdio.h>
#include <stdlib.h>
typedef struct lnode* list;
struct lnode
{
elementtype data; //输入数据；存于结构体中；
list next; //定义一个指针，指向下一个结点；
};
struct lnode l; //定义一个结构体对象
list ptrl; //定义一个结构体指针
int length(list ptrl) //求链表长度，传入起始结构体对象的指针
{
list p = ptrl; //p来表示起始指针
int j = 0; //用j来计数
while(p) //循环直到p为空
{
p = p->next; //往后传递
j++; //计数增加
}
return j; // 返回计数值，时间性能O(n)。
}
//按序号查找：
list findkth(int k, list ptrl) //传入序号与起始指针
{
list p = ptrl; //中间量
int i = 1;
while(p != NULL && i<k)
{
p = p->next;
i++;
}
if(i == k)
return p;
else
return NULL;
}
//按值查找：
list find(elementtype x, list ptrl)
{
list p = ptrl;
while(p != NULL && p->data != x)
p = p->next;
return p;
}
list insert(elementtype x, int i, list ptrl)
{
list p,s;
if(i == 1) //考虑放在起始位置的情况
{
s = (list)malloc(sizeof(struct lnode));
s->data = x;
s->next = ptrl;
return s;
}
p = findkth(i-1, ptrl); //不在起始位置，先找到i-1的位置
if(p == NULL)
{
printf(“参数i错”)；
return NULL;
}
else
{
s = (list)malloc(sizeof(struct lnode));
s->data = x;
s->next = p->next; //令s中的传递指针指向原第i个元素的传递传递指针
p->next = s; //修改p（第i-1个结点）的传递指针
return ptrl;
}
}
list delete(int i, list ptrl) //删除对象的序号传入
{
list p, s;
if(i == 1) //删除起始位置的情况
{
s = ptrl;
if(ptrl != NULL)
ptrl = ptrl->next; //修改起始位置指针
else return NULL;
free(s);
return ptrl;
}
p = findkth(i-1, ptrl); //非删除起始位置，先找到i-1的位置
if(p == NULL) //如果i-1位置不存在，那i的位置一定不存在
{
printf(“第%d个结点不存在”,i-1);
return NULL;
}
else if(p->next == NULL) //i-1的位置存在，但i位置不存在
{
printf(“第%d个结点不存在”, i);
return NULL;
}
else
{
s = p->next;
p->next = s->next;
free(s);
return ptrl;
}
}