就是这样的。
线性表的特点就是长度可变，如果使用常规的数组，就不能实现这个特性，因为数组是定长的。而在堆中申请的内存可以通过参数在运行时指定它的大小，且可以调整它的大小，并且其使用方式和数组一样，使用索引访问。
int*p = (int*)malloc(sizeof(int)*5)
p[0] //第一个元素
p[1] //第二个元素
p[2] //第三个元素
//...
free(p)
链表1。是由结构体和指针构成的。
2。包括两个部分一个是数据域和指针域。
3。链表中的结点分为两类：头结点和一般结点。头结点是没有数据域的。
4。基本操作有：初始化链表，增加结点和删除结点，求链表的长度等等。
struct Linknode{
int data
struct Linknode *next
}
这个地方有个知识点：这个是链表的数据结构是有结构体和指针构成。结构体名为Linknode.但这里面没有定义结构体变量，只有我们定义了结构体变量才能使用结构体。
结构体变量怎么定义呢？
有两种方式：
1。struct Linknode Linklist
2.typedef struct linknode Linklist.
一般我们都希望采用第2种，这样的好处是: 当我们再定义结构体变量时，可以用：Linklist p而如果我们采用第一种还必须采用 struct Linknode p对比一下就可以知道第2种要简单很多。那么下面我们都采用第2种方式来定义结构体变量。
上面我们已经定义了一个链表：
1。初始化链表。
#include
#include
int InitLinkList(Linklist **Lnode)
{
*Lnode=(Linklist)malloc(sizeof(Linklist))//*Lnode等于L，对与*Lnode的分配空间相当与对主函数中的L分配空间。
if(!*Lnode)
return 0
（*Lnode）->next=NULL
}
在初始化链表的时候，我们用到了2级指针为什么呢？因为我们希望在InitLinkList函数生成的头结点，主函数中也能指向这个头结点。如果我们用一级指针的话，用malloc分配空间的时候，它将会返回分配空间的首地址给指针变量Lnode，而不能使是的空间被主函数中指针变量L得到这个地址。所以我们要用2级指针。
void main()
{
Linklist *L
InitLikList(&L)
}
2。增加链表结点
增加链表结点其实很简单，一般用到三个结构体指针变量和一个循环结构。
InsertLinkList(Linklist *Lnode)
{
Linklist *p,*q
int d
{
scanf("%d",&d)
if(d==-9999)
break
p=Lnode->next//p指向头结点
//通过while循环和指针变量p定位要插入的结点q的位置。
while（p）
p=p->next
//生成一个要插入的结点
q=(Linklist)malloc(sizeof(Linklist))//申请要插入的结点空间
q->data=d//填充要插入结点的数据域
q->next=p->next//首先填充要插入结点q的指针域进行填充。
p->next=q//然后把定位好的p指针域进行修改指向q.
}while(9)//循环退出的条件是输入的数据-9999
}
void main()
{
Linklist *L
InitLinkList(&L)//生成一个头结点
InsertLinkList(L)//插入结点
}
3。求链表的长度：
int LengthLinkList(Linklist *Lnode)
{
int i=0
Linklist *p
p=Lnode->next//p指向链表的第一个结点。
while(p)
{
i++
p=p->next
}
return i
}
void main()
{
Linklist *L
InitLinkList(&L)//生成一个头结点
InsertLinkList(L)//插入一个结点
LengthLinkList(L)//求链表的长度。
}
4.删除结点
删除链表结点其实很简单，一般用到三个结构体指针变量和一个循环结构。
DestroyLinkList(Linklist *Lnode)
{
Linklist *p,*q
p=Lnode//p指向链表的头结点
while(p)
{
q=p->next//q指向当前结点的下一个结点。
free(p)//释放当前结点
p=q//p指向下一个结点
}
}
void main()
{
Linklist *L
InitLinkList(&L)//生成一个头结点
InsertLinkList(L)//插入结点
LengthLinkList(L)//求链表的长度。
DestroyLinkList(L)//删除链表结点
}
直接上源码吧。/*线性表功能的实现*/
#include<stdio.h>
//定义常量 存储空间的初始化分配
#define MAXSIZE 20
#define TRUE 1
#define ERROR -1
#define FALSE 0
#define OK 1
//用typedef定义类型
typedef int Status
typedef int ElemType
//定义一个结构体类型
typedef struct{
ElemType data[MAXSIZE]
int length
} SqList
//初始化函数
Status initList(SqList *L){
L->length = 0
return OK
}
//返回线性表的长度
Status getListLength(SqList L){
return L.length
}
//线性表为空返回true,否则返回false
Status listEmpty(SqList L){
if(L.length == 0){
return TRUE
}
return FALSE
}
//线性表清空,长度为0
Status clearList(SqList *L){
L->length = 0
return OK
}
//获取指定的元素的值,返回下标为i - 1的元素,赋值给e
Status getElem(SqList L, int i, ElemType *e){
//判断元素位置是否合法[i]
if(i >L.length || i <1){
printf("查找的位置不正确 \n")
return ERROR
}
//判断线性表是否为空
if(listEmpty(L)){
return ERROR
}
*e = L.data[i - 1]
return OK
}
//在线性表中查找指定的e相等的元素,如果查找成功,返回该元素的下标,否则返回ERROR
Status locateElem(SqList L, ElemType e){
int i
for(i = 0i <L.length - 1i++){
if(L.data[i] == e){
return i
}
}
printf("没有查找到元素 %d 指定的下标\n",e)
return ERROR
}
//自动创建 MAXSIZE 个元素,并赋值为0
Status createList(SqList *L){
int i
for(i = 0i <10i++){
L->data[i] = 0
}
L->length = 10
return OK
}
//在线性表中第i个位置前插入新元素e
Status listInsert(SqList *L, int i, ElemType e){
//判断长度是否可以允许插入新的数据
if(L->length >= MAXSIZE){
printf("空间已满,不能再插入数据\n")
return FALSE
}
//判断插入位置的合法性
if(i <1 || i >L->length) {
printf("插入位置不正确\n")
return FALSE
}
int j
for(j = L->length - 1j >= ij--){
L->data[j] = L->data[j - 1]
}
L->data[i - 1] = e
L->length++
return TRUE
}
//删除线性表中第i个元素,成功后表长减1,用e返回其值
Status deleteList(SqList *L, int i, ElemType *e){
//判断线性表是否为空
if(listEmpty(*L)){
return ERROR
}
//判断删除的位置是否合法
if(i <1 || i >L->length) {
printf("删除位置不合法\n")
return ERROR
}
*e = L->data[i - 1]
for(ii <L->lengthi++){
L->data[i - 1] = L->data[i]
}
L->length--
return TRUE
}
//遍历线性表
Status listTraverse(SqList L){
int i
for(i = 0i <L.lengthi++){
printf("%d ",L.data[i])
}
printf("\n")
return OK
}
//主程序
int main(void){
SqList L
ElemType e
initList(&L)
int option = 1
int input_number
int res
ElemType input_value
printf("\n1.遍历线性表 \n2.创建线性表 \n3.清空线性表 \n4.线性表插入 \n5.查找表中元素 \n6.判断元素是否在表中 \n7.删除某个元素 \n8.线性表长度\n9.线性表是否为空\n0.退出 \n请选择你的操作：\n")
while(option){
scanf("%d",&option)
switch(option){
case 0:
return OK
break
case 1:
listTraverse(L)
break
case 2:
createList(&L)
listTraverse(L)
break
case 3:
clearList(&L)
listTraverse(L)
break
case 4:
printf("请输入插入的位置:")
scanf("%d",&input_number)
printf("\n")
printf("请输入插入的值:")
scanf("%d",&input_value)
printf("\n")
listInsert(&L, input_number, input_value)
listTraverse(L)
break
case 5:
printf("请输入要查找的位置:")
scanf("%d",&input_number)
printf("\n")
getElem(L, input_number, &input_value)
printf("第%d个元素的值为:%d\n",input_number,input_value)
break
case 6:
printf("请输入要查找的元素:")
scanf("%d",&input_value)
printf("\n")
res = locateElem(L, input_value)
if(res != ERROR){
printf("值为%d在表中的第%d个位置\n",input_value,input_number)
}
break
case 7:
printf("要删除第几个元素？")
scanf("%d",&input_number)
printf("\n")
deleteList(&L, input_number, &input_value)
listTraverse(L)
break
case 8:
res = getListLength(L)
printf("线性表的长度是:%d",res)
break
case 9:
res = listEmpty(L)
if(res){
printf("线性表的是空的")
}else{
printf("线性表的是不是空的")
}
break
}
}
return OK
}
线性表的特征是:
1. 元素之间是有序的,如果元素存在多个,则第一个元素无前驱,最后一个无后继,其它元素都有且只有一个前驱和后继.
2. 元素个数是有限的. 当n=0是,称为空表
线性表实现方式有两种,分别是顺序存储结构和链式存储结构,它们之间各有优缺点 . 根据需求的不同进行选择不同的存储结构.
线性表存储结构的优缺点
优点:
1. 无须为表中元素之前的逻辑关系而增加额外的存储空间
2. 可以快速的存取表中的任一位置的元素
缺点:
1. 插入和删除操作需要移动大量元素
2. 当线性表长度变化较大时,难以确定存储空间的容量.
3. 造成存储空间的”碎片”.
