数据结构之线性表

发表于 2020-02-15 更新于 2021-02-04 分类于数据结构

线性表是一种最基本的数据结构，下面是线性表的顺序存储方式（以下代码均参考《大话数据结构》，运行环境dev c++5.11）

#include<stdio.h>
#include<malloc.h>
#define MAXSIZE 100
typedef int ElementType;
typedef struct LNode *List;
struct LNode{
ElementType Data[MAXSIZE];
int Last;
}; 
List L;

List MakeEmpty();
int Find(ElementType X,List L);
void Insert(ElementType X,int i,List L);
void Delete(int i,List L);
ElementType FindKth(int K,List L);

//初始化
List MakeEmpty(){
List L;
L=(List)malloc(sizeof(struct LNode));
L->Last=-1;
return L;
}
//按值查找 
int Find(ElementType X,List L){
int i=0;
while(i<=L->Last&&L->Data[i]!=X)
    i++;
if(L->Last<i)
    return -1;
    else 
    return i;
}

//插入,下面的为头插法 
void Insert(ElementType X,int i,List L){
int j;
if(L->Last==MAXSIZE-1){
    printf("表满");
    return;
}
if(i<0||L->Last+1<i){
    printf("位置不合法");
    return; 
}
for(j=L->Last;j>=i;j--)
    L->Data[j+1]=L->Data[j];
    L->Data[i]=X;
    L->Last++;
    return;
} 

void Delete(int i,List L){
int j;
if(i<0||L->Last<i){
    printf("L->Data[%d]不存在元素",i);
    return;
}
for(j=i;j<L->Last;j++)//删除第i个元素，实际上对应的下标是i-1 
    L->Data[j-1]=L->Data[j];
    L->Last--;
    return; 
}
ElementType FindKth(int K,List L){
if(K<0||L->Last<K){
    printf("L->Data[%d]不存在元素",K);
    return;
}
return L->Data[K];
}
int Length(List L){
return L->Last+1;
}
int main(){
int i=0;
L=MakeEmpty();
Insert(11,0,L);
printf("在线性表L->Data[0]插入11\n");
Insert(25,0,L);
printf("在线性表L->Data[0]插入25\n");
Insert(33,0,L);
printf("在线性表L->Data[0]插入33\n");
Insert(77,0,L);
printf("在线性表L->Data[0]插入77\n");
printf("此时线性表为；");
for(i=0;i<Length(L);i++)
    printf("%d",L->Data[i]);
printf("\n");
printf("查找值为12的下标为：%d\n",Find(12,L));
printf("下标为3的线性表的值是：%d\n",FindKth(3,L));
Delete(2,L);
printf("删除下标为2的元素\n"); 
Delete(2,L);
printf("删除下标为2的元素\n");  
    printf("此时线性表为；");
for(i=0;i<Length(L);i++)
    printf("%d",L->Data[i]);
printf("\n");
return 0;
}

以下是线性表的链式存储结构

#include<stdio.h>
#include<malloc.h>
typedef int ElementType;
typedef struct LNode *List;
struct LNode{
ElementType Data;
List Next;
};
List L;
List MakeEmpty();
int Length(List);
List FindfKth(int K,List L);
List Find(ElementType X,List L);
List Insert(ElementType X,int i,List L);
List Delete(int i,List L);
void Print(List L);

List MakeEmpty(){
List L=(List)malloc(sizeof(struct LNode));
L=NULL;
return L;
}

int Length(List L){
List p=L;
int len=0;
while(p){
    p=p->Next;
    len++;
}
return len;
}
List FindKth(int K,List L){
List p=L;
int i=1;
while(p&&i<K){
    p=p->Next;
    i++;
}
if(i==K)
    return p;
else
    return NULL;
}
List Find(ElementType X,List L){
List p=L;
while(p&&p->Data!=X)
    p=p->Next;
return p;
}
List Insert(ElementType X,int i,List L){
List p,s;
if(i==1){
    s=(List)malloc(sizeof(struct LNode));
    s->Data=X;
    s->Next=L;
    return s;
}
p=FindKth(i-1,L);
if(!p){
    printf("结点错误");
    return NULL; 
}else{
    s=(List)malloc(sizeof(struct LNode));
    s->Data=X;
    s->Next=p->Next;
    p->Next=s;
    return L;
}
}
List Delete(int i,List L){
List p,s;
if(i==1){
    s=L;
    if(L)
        L=L->Next;
    else
        return NULL;
    free(s);
    return L;
}
p=FindKth(i-1,L);
if(!p||!(p->Next)){
    printf("结点错误");
    return NULL; 
}else{
    s=p->Next;
    p->Next=s->Next;
    free(s);
    return L;
}
}
void Print(List L){
List t;
int flag=1;
printf("当前链表为：");
for(t=L;t;t=t->Next){
    printf("%d",t->Data);
    flag=0;
} if(flag)
    printf("NULL");
printf("\n");
}
int main(){
L=MakeEmpty();
Print(L);
L=Insert(11,1,L);
L=Insert(25,1,L);
L=Insert(32,1,L);
L=Insert(77,1,L);
Print(L);
printf("当前链表长度：%d\n",Length(L));
printf("当前链表中第二个结点的值是：%d\n",FindKth(2,L)->Data);
printf("查询22是否在该链表中：");
if(Find(22,L))
    printf("是\n");
else
    printf("否\n");
printf("查询33是否在该链表中：");
if(Find(33,L))
    printf("是\n");
else
    printf("否\n");
L=Delete(1,L);
L=Delete(3,L);
printf("------------删除后---------\n");
Print(L);
return 0; 
          
}

以下是栈的链式存储结构

#include<stdio.h>
#include<stdlib.h>
#include<io.h>
#include<math.h>
#include<time.h>

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20

typedef int Status;
typedef int SElemType;

//链栈的结构,也可参考线性表的链式存储，效果是一样的 
typedef struct StackNode{//定义结点 
SElemType data;
struct StackNode *next;
}StackNode, *LinkStackPtr;

typedef struct {//定义一个栈 
LinkStackPtr top;//定义了一个指向结点的指针
int count; 
}LinkStack;

Status visit(SElemType c){
printf("%d ", c);
return OK;
} 

//构造一个空栈
Status InitStack(LinkStack *S){
S->top = (LinkStackPtr)malloc(sizeof(StackNode));
if(!S->top)
    return ERROR;
    S->top = NULL;
    S->count = 0;
    return OK;
} 

//把S置为空栈
Status ClearStack(LinkStack *S){
LinkStackPtr p, q;//定义两个指向结点的指针 
p = S->top;
while(p){
    q = p;
    p = p->next;
    free(q);
}
S->count = 0;
return OK; 
} 

//判断是否为空
Status StackEmpty(LinkStack S){
if(S.count == 0)
    return TRUE;
else 
    return FALSE;
} 

//返回栈的长度
int StackLength(LinkStack S){
return S.count; 
} 

//用e返回栈顶元素
Status GetTop(LinkStack S, SElemType *e){
if(S.top == NULL)
    return ERROR;
else
    *e = S.top->data;
return OK;
} 

//插入元素为e的栈顶元素
Status Push(LinkStack *S, SElemType e){
LinkStackPtr s=(LinkStackPtr)malloc(sizeof(StackNode));
s->data = e;
s->next = S->top;
S->top = s;
S->count++;
return OK;
} 

//删除栈顶的元素，并用e返回
Status Pop(LinkStack *S, SElemType *e){
LinkStackPtr p;//先找结点再删除 
if(StackEmpty(*S))
    return ERROR;
*e = S->top->data;
p = S->top;
S->top = S->top->next;
free(p);
S->count--;
return OK; 
} 

//从顶开始访问
Status StackTraverse(LinkStack S){
LinkStackPtr p;
p=S.top;
while(p){
    visit(p->data);
    p = p->next;
}
printf("\n");
return OK;
} 

int main(){
int j;
LinkStack s;
int e;
if(InitStack(&s) == OK)
    for(j = 1; j <= 10; j++)
        Push(&s, j);
printf("栈中元素依次为: ");
StackTraverse(s);
Pop(&s, &e);
printf("弹出栈顶元素 e = %d\n",e);
printf("栈空否: %d(1:空 0:否)\n",StackEmpty(s));
GetTop(s,&e);
printf("栈顶元素 e = %d 栈的长度为%d\n", e,StackLength(s));
ClearStack(&s);
printf("清空后，栈空否: %d(1:空 0:否)\n",StackEmpty(s));
return 0;
}

以下是斐波那契数列的两种计算方法，注意体会迭代和递归的含义，当使用递归的方法的时候，对计算机内存的占用是非常大的

#include<stdio.h>

int F(int i){
if(i < 2)
    return i == 0 ? 0 : 1;
return F(i - 1) + F(i - 2); 
}
int main(){
int i;
int a[40];
printf("迭代显示斐波那契数列：\n");
a[0] = 0;
a[1] = 1;
printf("%d ", a[0]);
printf("%d ", a[1]);
for(i = 2; i < 40; i++){
    a[i] = a[i - 1] + a[i -2];
    printf("%d ", a[i]);
} 
printf("\n");

printf("递归显示斐波那契数列：\n");
for(i = 0; i < 40; i++)
    printf("%d ", F(i));
return 0;
}