(C语言)单链表的顺序实现(数据结构一)-白红宇

(C语言)单链表的顺序实现(数据结构一)

阅读量：5256 次

发布时间：2019-06-14

本文共 5640 字，大约阅读时间需要 18 分钟。

1.数据类型定义

在代码中为了清楚的表示一些错误和函数运行状态，我们预先定义一些变量来表示这些状态。在head.h头文件中有如下定义：

//定义数据结构中要用到的一些变量和类型#ifndef HEAD_H#define HEAD_H#include 
    
     #include 
     
      #include 
      
       #define TRUE  1#define FALSE 0#define OK    1#define ERROR  0#define INFEASIBLE -1#define OVERFLOW   -2    //分配内存出错typedef int  Status;     //函数返回值类型typedef int  ElemType;   //用户定义的数据类型#endif

2.单链表数据结构实现

为了实现单链表，我们定义结构体 LinearList，具体代码如下：

typedef struct{	ElemType *elem;   //存放数据	int length;      //链表长度	int listsize;    //链表容量}LinearList;

3.链表方法摘要

Status InitList(LinearList & L);    //初始化链表Status DestroyList(LinearList &L);   //销毁链表Status ClearList(LinearList &L);     //清空链表Status ListEmpty(LinearList L);      //链表是否为空Status ListLength(LinearList L);     //链表长度Status GetElem(LinearList L,int i,ElemType &e);  //获得链表第i位置的长度，返回给eStatus LocateElem(LinearList L,ElemType e,Status(*comp)(ElemType,ElemType)); //链表中满足comp条件的数据的位置Status PriorElem(LinearList L,ElemType cur_e,ElemType &per_e)  // cur_e的前一个数据Status NextElem(LinearList L,ElemType cur_e,ElemType &next_e);  //cur_e的后一个数据Status ListInsert(LinearList &L,int i,ElemType e);    //在第i个位置插入eStatus ListDelete(LinearList &L,int i,ElemType &e);   //删除第i位置数据，并给eStatus Union(LinearList &La,LinearList Lb);     //La=la并LbStatus MergeList(LinearList La,LinearList Lb,LinearList &Lc);  //La和Lb从小到大排序后给LcStatus MergeList_pt(LinearList La,LinearList Lb,LinearList &Lc);  //La和Lb从小到大排序后给Lc,指针实现

4.单链表顺序实现

在LinearList.h文件中实现单链表的方法，具体代码如下：

#ifndef LINEARLIST_H#define LINEARLIST_H#include "head.h"#define LIST_INIT_SIZE  100  //初始化链表大小#define LIST_INCERMENT  10   //链表容量增加基本单元typedef struct{	ElemType *elem;   //存放数据	int length;      //链表长度	int listsize;    //链表容量}LinearList;Status equal(int a,int b){	return a==b;}Status InitList(LinearList & L){	L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));	if (!L.elem) return OVERFLOW;	L.length=0;	L.listsize=LIST_INIT_SIZE;	return OK;}Status DestroyList(LinearList &L){	free(L.elem);	L.elem=NULL;	L.length=0;	L.listsize=0;	return OK;};Status ClearList(LinearList &L){	L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));	if (!L.elem) return OVERFLOW;	L.length=0;	L.listsize=LIST_INIT_SIZE;	return OK;}Status ListEmpty(LinearList L){	return L.length==0;}Status ListLength(LinearList L){	return L.length;}Status GetElem(LinearList L,int i,ElemType &e){	if (i<1 || i>L.length) return ERROR;	e=L.elem[i-1];	return OK;}Status LocateElem(LinearList L,ElemType e,Status(*comp)(ElemType,ElemType)){	int i=0;	for (;i
    
     length+1) return ERROR;	if (length>=L.listsize){		ElemType *newBase=(ElemType*)realloc(L.elem,(L.listsize+LIST_INCERMENT)*sizeof(ElemType));		if(!newBase) return OVERFLOW;		L.elem=newBase;		L.listsize+=LIST_INCERMENT;	}	ElemType *q=&L.elem[i-1];	ElemType *p=&L.elem[length];	while(q<=p){		*(p+1)=*p;		p--;	}	*q=e;	++L.length;	return OK;};Status ListDelete(LinearList &L,int i,ElemType &e){	if(i<1 ||i>L.length) return ERROR;	ElemType *p=&L.elem[i-1];	ElemType *q=&L.elem[L.length-1];	e=*p;	while(p<=q){		*p=*(p+1);		++p;	}	--L.length;	return OK;}Status Union(LinearList &La,LinearList Lb){	int la_l=ListLength(La);	int lb_l=ListLength(Lb);	for (int i=1;i<=lb_l;i++)	{		ElemType e=0;		GetElem(Lb,i,e);		if(!LocateElem(La,e,equal)){			int l=ListLength(La);			ListInsert(La,++l,e);		}	}	return OK;}Status MergeList(LinearList La,LinearList Lb,LinearList &Lc){	int La_l=ListLength(La);	int Lb_l=ListLength(Lb);	InitList(Lc);	int i=1,j=1,k=1;	while(i<=La_l&&j<=Lb_l){		ElemType La_e,Lb_e;		GetElem(La,i,La_e);		GetElem(Lb,j,Lb_e);		if (La_e<=Lb_e)		{			ListInsert(Lc,k++,La_e);			i++;		}else{			ListInsert(Lc,k++,Lb_e);			j++;		}	}	while(i<=La_l){		ElemType La_e;		GetElem(La,i,La_e);		ListInsert(Lc,k++,La_e);		i++;	}	while(j<=Lb_l){		ElemType Lb_e;		GetElem(Lb,j,Lb_e);		ListInsert(Lc,k++,Lb_e);		j++;	}	return OK;}Status MergeList_pt(LinearList La,LinearList Lb,LinearList &Lc){	int pc_l=La.length+Lb.length;	Lc.elem=(ElemType*)malloc(sizeof(ElemType)*pc_l);	Lc.length=pc_l;	Lc.listsize=pc_l;	if (!Lc.elem) return OVERFLOW;	ElemType* pa=La.elem;	ElemType* pb=Lb.elem;	ElemType* pc=Lc.elem;	ElemType* pa_last=pa+La.length-1;	ElemType* pb_last=pb+Lb.length-1;	while(pa<=pa_last&&pb<=pb_last){		if(*pa<=*pb){			*pc++=*pa++;		}else{			*pc++=*pb++;		}	}	while(pa<=pa_last){		*pc++=*pa++;	}	while(pb<=pb_last){		*pc++=*pb++;	}	return OK;}#endif

5.单链表测试

#include "LinearList.h"void main(){	LinearList L;	InitList(L);                //初始化链表	for (int i=1;i<10;i++)		   ListInsert(L,i,i);   //向链表中插入数据	printf("\n链表L中数据：");	for(int i=1;i
    
     ",e);	}	printf("end");	ElemType e;	ListDelete(L,5,e);             //删除第5位置数据	printf("\n删除第5位置数据为：%d",e);	PriorElem(L,6,e);               //前一个数据	printf("\n6的前一个数据：%d",e);	NextElem(L,6,e);                 //后一个数据	printf("\n6的后一个数据：%d",e);		printf("\n链表中数据：");	for(int i=1;i
     
      ",e);	}	printf("end\n");	LinearList Lb;	LinearList Lc;	InitList(Lb);	for(int i=1;i<10;i++)		ListInsert(Lb,i,i+5);	printf("\n链表Lb中数据：");	for(int i=1;i
      
       ",e);	}	printf("end\n");	Union(L,Lb);    //L=L并Lb	printf("\n链表L中数据：");	for(int i=1;i
       
        ",e);	}	printf("end");	//MergeList(L,Lb,Lc);    //测试MergeList()	MergeList_pt(L,Lb,Lc);  //测试MergeList_pt()	printf("\n链表Lc中数据：");	for(int i=1;i
        
         ",e);	}	printf("end\n");}

6.测试结果

链表L中数据：1->2->3->4->5->6->7->8->end删除第5位置数据为：56的前一个数据：46的后一个数据：7链表中数据：1->2->3->4->6->7->8->end链表Lb中数据：6->7->8->9->10->11->12->13->end链表L中数据：1->2->3->4->6->7->8->9->10->11->12->13->end链表Lc中数据：1->2->3->4->6->6->7->7->8->8->9->9->10->10->11->11->12->12->13->13->14->end