C语言实现线性表

• 前言
• 一、基于数组的顺序表
• • 1、实现
  • 2、测试代码
• 二、基于链式存储的线性表
• • 1、实现
  • 2、测试代码
• 三、测试结果
• 总结

本篇博客使用c、c++实现了线性表的增删改查，实现方式分为链表与顺序表 。代码复制粘贴可运行。
后续算法均基于本博客cpp 文件"sqlist"与"linknode"实现。

//本文件为 sqlist，main函数随后
#include 
#include 
#include 
//#define MAXSIZE 100
typedef int ElemType;
using namespace std;


typedef struct SqList{
		ElemType data[100];
		int length;
}SqList;

void InitList(SqList * &L)
{
	//L=new (SqList);
	L=(SqList *)malloc(sizeof(SqList));
	L->length=0;
}
void CrearList(SqList * &L)
{
	int n;
	cout<<"请输入您需要储存元素的数量"<>n;
    L->length=n;
    cout<<"请输入您需储存的元素"<length;i++)
    {
		ElemType x;
		cin>>x;
    	L->data[i]=x;
	}
}

void DestroyList(SqList *&L)
{
	free(L);
}

bool ISEmpty(SqList *&L)
{
	return L->length==0;
}

int ListLength(SqList *&L)
{
	return L->length;
}

void DispList(SqList *&L)
{
	if(L->length>0)
	{
		cout<<"表中的值为："<length;i++)
				{
					cout<data[i]<0&&i<=L->length)
	{
	e = L->data[i-1];
	return true;
	}
	else
	return false;
}

bool LocateElem(SqList *&L,ElemType e)//若存在e，则返回True
{
		for(int i=0;ilength;i++)
	{
		if(L->data[i]==e)
	        return true;
		else
	     	return false;
	}
}

bool ListInsert(SqList *&L,int i,ElemType e)//将值为e的元素插在第i个位置
{
	if(i<0||i>L->length)
		return -1;
	else
	{
		int j=i-1;
		for(int k=L->length-1;k>j;k--)//1 2 3 4 5
	  		L->data[k+1]=L->data[k];
			L->data[j]=e;
			L->length++;
	}
	return 0;
}

bool ListDelete(SqList *&L,int i,ElemType &e)//将第i个位置的值用e返回并删除i
{
 	 if(i<0||i>L->length)
	  		 return false; // 1 2 3 4 5 5 5
     else
	   {
	     	e=L->data[i-1];
	     	for(int j=i-1;jlength-1;j++)
	     	L->data[j]=L->data[j+1];
	     	L->length--;
	   }
	   return 0;
}

//main函数测试代码：
int main(){
	SqList *L;
	InitList(L);
	CrearList(L);
		cout<<"表的长度为:"< 
二、基于链式存储的线性表 
1、实现 
//本文文件为
#include 
#include 
#include 
#include 
//#define MAXSIZE 100
typedef int ElemType;
using namespace std;


typedef struct linkNode{
		ElemType data;
		struct linkNode *next;
}linkNode;

void InitList(linkNode * &L)
{
	//L=new (linkNode);
	L=(linkNode *)malloc(sizeof(linkNode));
	L->next=NULL;
}

void CrearListR(linkNode * &L,ElemType a[],int n)//用a[]初始化链表，n为数组长度,尾插法实现
{
	 L=(linkNode *)malloc(sizeof(linkNode));
	 L->next=NULL;
	 linkNode *s;
     linkNode *r=L;
	 for(int i=0;idata=a[i];
		r->next=s;
	//	s->next=NULL;
		r=s;
	 }
	  r->next=NULL;
}

void CreatListF(linkNode * &L,ElemType a[],int n)//头插法建立链表
{
	 L=(linkNode *)malloc(sizeof(linkNode));
	 L->next=NULL;
	 linkNode *p=L;
	 linkNode *s;
	 for(int i=0;idata=a[i];
	 	 s->next=p->next;
	 	 p->next=s;
	 }
}

void DestroyList(linkNode *&L)
{
	linkNode *pre=L,*p=pre->next;
	while(p!=NULL)
	{
		free(pre);
		pre=p;
		p=pre->next;
	}
	free(pre);//此时p指向NULL，而pre指向尾结点
}

void DispList(linkNode *&L)//打印链表需建立在链表非空情况下
{
	linkNode *p=L->next;
	 while(p!=NULL)
	 {
		cout<data<next;
	 }
}

bool ISEmpty(linkNode *&L)
{
	return L->next==NULL;
}

int ListLength(linkNode *&L)
{
	int length=0;
    linkNode *p=L->next;
    while(p!=NULL)
    {
    	length=length+1;
    	p=p->next;
	}
	return length;
}

bool GetElem(linkNode *&L,int i,ElemType &e)//注意此处e为引用传递
{
	 if(i<=0)
	 return false;
	 else
	 {
	 	int j=1;
	    linkNode *p=L->next;//此处有多种写法：j=0/p=L/jnext;
			j++;
		}
		if(p!=NULL)
		{
            e=p->data;
            return true;
		}
		else
			return false;
	 }
}

bool LocateElem(linkNode *&L,ElemType e)//若存在e，则返回True、、此函数可写成返回e的位置
{
	 linkNode *p=L->next;
	 while(p!=NULL)//此处可写成p->data!=e
	 {
	 	if(p->data==e)
	 	return true;
	 	else
	 	p=p->next;
	 }
}

bool ListInsert(linkNode *&L,int i,ElemType e)//将值为e的元素插在第i个位置
{
	if(i<=0)
	return false;
	else
	{
		 int j=0;//此处不同与GetElem
 	     linkNode *p=L;//因存在操作第一个元素的可能，故此处 p 不能赋值 L-1
		 while(p!=NULL&&jnext;
		 	j=j+1;
		 }
		 if(p!=NULL)
		 {
    	    linkNode *s=(linkNode *)malloc(sizeof(linkNode));
 			s->data=e;
		 	s->next=p->next;
	 		p->next=s;
		 	 return true;
		 }
		 else
		 	 return false;
	}

	 
}

bool ListDelete(linkNode *&L,int i,ElemType &e)//将第i个位置的值用e返回并删除i
{
	if(i<=0)
	return false;
	 int j=1;
	 linkNode *p=L,*s;
	 while(p!=NULL&&jnext;
	 	j=j+1;
	 }
	 if(p==NULL)
        return false;
	 else
	 {
	 	//linkNode *s=(linkNode *)malloc(sizeof(linkNode));
	 	s=p->next;
	 	if(s==NULL)
		   return false;
	 	e=s->data;
	 	p->next=s->next;
	 	free(s);
	 	return true;
	 }
	 
}
 
2、测试代码 
int main(){
	linkNode *L;
	
	InitList(L);
	ElemType a[10]={1,2,3,4,5,6,7,8,9,10};
	CrearListR(L,a,10);
        cout<<"表的长度为："< 
三、测试结果 
 
 
 
总结 
 之后的博客将看到一些算法逐步求精的过程，他们的存储结构将基于上述实现。还请大家发现、纠正可能存在的错误！感谢阅读本篇博客！