C语言中顺序列表的插入删除程序

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#define MaxSize 50

#define len(x) sizeof(x)/sizeof(x[0])

typedef struct SqList

{

int data[MaxSize]

int length

}SqList

static SqList Create(int a[],int n)//用一个数组创建静态顺序表

static void Print(SqList L)//打印一个静态顺序表

static void ListInsert(SqList *p,int i,int e)//L的第i个位置插入e

static void ListDelete(SqList *p,int i)//删除列表第i个数据

static int LocateElem(SqList L,int e)//查找第一个值等于e的元素,返回其位序

static void Reverse(SqList *p,int left,int right)//逆置表的第left到right的元素顺序

/*递增序列折半查找等于e的元素,返回其位序*/

static int Binsearch(SqList L,int e)

int main()

{

int a[]={1,2,3,4}

SqList L=Create(a,len(a))

ListInsert(&L,2,100)

ListDelete(&L,2)

Reverse(&L,1,4)

Print(L)

printf("%d\n",Binsearch(L,2))

}

static SqList Create(int a[],int n)

{

SqList L

int i

L.length=n

for(i=0i<L.lengthi++)

L.data[i]=a[i]

return L

}

static void Print(SqList L)

{

int i

for(i=0i<L.lengthi++)

printf("%d ",L.data[i])

printf("\n")

}

static void ListInsert(SqList *p,int i,int e)

{

int j

if(i<1 || i>p->length+1)

{printf("错误范围\n")}

if(p->length>=MaxSize)

{printf("存储空间已满\n")}

for(j=p->lengthj>=ij--)

p->data[j]=p->data[j-1]

p->data[i-1]=e

p->length++

}

static void ListDelete(SqList *p,int i)

{

if(i<1 || i>p->length)

{printf("删除范围出错\n")return}

while(i<p->length)

{

p->data[i-1]=p->data[i]i++

}

p->length--

}

static int LocateElem(SqList L,int e)

{

int i

for(i=0i<L.lengthi++)

if(L.data[i]==e)

return i+1

return 0

}

static void Reverse(SqList *p,int left,int right)

{

int temp

if(left>right || left<1 || right>p->length)

{printf("错误的输入\n")return}

for(left--,right--left<rightleft++,right--)

{

temp=p->data[left]

p->data[left]=p->data[right]

p->data[right]=temp

}

}

static int Binsearch(SqList L,int e)

{

int mid,low=0,high=L.length-1

while((low+1)!=high)

{

mid=(low+high)/2

if(L.data[mid]==e) return mid+1

if(e<L.data[mid]) high=mid

if(e>L.data[mid]) low=mid

}

return 0

}

ListInsert 和 ListDelete 为你所要的函数

#include <time.h>

#include <stdio.h>

#define NULL -2

#define ERROR -1

#define OK 1

#define TRUE 2

#define FALSE 3

#define Boolen int

#define Status int

#define LIST_INIT_SIZE 3

#define LIST_INCREMENT 2

#define NAME_LEN 13

#define DES_LEN 30

char ErrDescription[DES_LEN]

typedef struct{

int NO

charName[NAME_LEN]

enum{male,female} Sex

int Age

charTel[15]

charInserttime[64]

}ElemType,*ElemPointer

typedef struct{

ElemPointer base //基址

intlength //表长

intlistsize//内存占用

intelemcount//记录数

}SqList,*SqPointer

int ErrorEXP(int i)

{

switch(i)

{ case 1: strcpy(ErrDescription,"InitList::(ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType)) 空间申请失败")break

case 2: strcpy(ErrDescription,"IncreaseList::(ElemType *)realloc(L->base,(L->length + LIST_INCREMENT) * sizeof(ElemType)) 空间申请失败")break

case 3: strcpy(ErrDescription,"if(!L->base) return ErrorSqList不存在")break

case 4: strcpy(ErrDescription,"GetElem:: i 越界")break

case 5: strcpy(ErrDescription,"ListInsert:: i 越界")break

case 6: strcpy(ErrDescription,"ListInsert:: CALL IncreaseList(L)==ERROR return Error 邻接空间申请失败，由ListInsert返回")break

case 7: strcpy(ErrDescription,"ListDelete:: i 越界")break

case 8: strcpy(ErrDescription,"KeyInList:: i 越界")break

case 9: strcpy(ErrDescription,"KeyInList:: CALL ListInsert(L,i,temp)==ERROR return Error 邻接空间申请失败，由KeyInList返回")break

case 10: strcpy(ErrDescription,"ScanfList:: CALL KeyInList(L,i++)==ERROR return Error")break

}

puts("!!!!!!!!!!!!!!! ERROR !!!!!!!!!!!!!!!\n")

puts(ErrDescription)

puts("\n!!!!!!!!!!!!!!! ERROR !!!!!!!!!!!!!!!\n")

return ERROR

}

Status InitList(SqPointer L)

{

L->base = 0//不可不要!!! 去掉后即使(ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType))失败，系统也会认为正常

L->base = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType))

if(!L->base) return ErrorEXP(1)//空间申请失败，返回

L->length = LIST_INIT_SIZE

L->listsize = L->length * sizeof(ElemType)

L->elemcount = 0

return OK

}

Status IncreaseList(SqPointer L)

{

ElemPointer newbase

newbase = (ElemType *)realloc(L->base,(L->length + LIST_INCREMENT) * sizeof(ElemType))

if(!newbase) return ErrorEXP(2)

L->base = newbase

L->length += LIST_INCREMENT

L->listsize = L->length * sizeof(ElemType)

return OK

}

Status DestroyList(SqPointer L)

{

if(!L->base) return ErrorEXP(3)//L不存在，返回

free(L->base)

L->length = NULL

L->listsize = NULL

L->elemcount = NULL

return OK

}

Status ClearList(SqPointer L)

{

if(!L->base) return ErrorEXP(3)//L不存在，返回

L->elemcount = 0

return OK

}

Boolen ListEmpty(SqPointer L)

{

if(!L->base) return ErrorEXP(3)//L不存在，返回

if(L->elemcount == 0)

return TRUE

else

return FALSE

}

int ListElemCount(SqPointer L)

{

if(!L->base) return ErrorEXP(3)//L不存在，返回

return L->elemcount

}

Status GetElem(SqPointer L,int i,ElemType *ret) //调用此函数需将ret指向main函数域某一ElemType变量

{

if(!L->base) return ErrorEXP(3)//L不存在，返回

if(i >L->elemcount) return ErrorEXP(4)//i越界，返回

*ret = L->base[i-1]//i 从1开始 此种方法在main中改变*ret会直接更改链表中数据

return OK

}

//重大发现 指针型 temp->base 普通型L.base

int LocateElem(SqPointer L,char Locatename[]) //返回的i从1开始

{

int i=0

ElemType *temp

if(!L->base) return ErrorEXP(3)//L不存在，返回

while(i<L->elemcount)

{

temp=&(L->base[i])//改为temp=L->base[i++]并去除下面的i++ ??

if(strcmp(temp->Name,Locatename) == 0) return i+1//不能用temp->Name==locatename来试图比较字符串

i++

}

return 0

}

Status ListInsert(SqPointer L,int i,ElemType newelem) //插入位置1<=i<=elemcount+1

{

ElemPointer newbase

ElemType *temp,*flag

if(!L->base) return ErrorEXP(3)//L不存在，返回

if(i<1 || i>L->elemcount + 1) return ErrorEXP(5)

if(L->elemcount == L->length)

if(IncreaseList(L)==ERROR) return ErrorEXP(6)

flag=&(L->base[i-1])//插入位置

for(temp=&(L->base[L->elemcount-1])temp>=flagtemp--)

*(temp+1)=*temp

*flag=newelem

L->elemcount++

return OK

}

Status ListDelete(SqPointer L,int i,ElemType *ret) //调用此函数需将ret指向main函数域某一ElemType变量

{

ElemType *temp

if(!L->base) return ErrorEXP(3)//L不存在，返回

if(i<1 || i>L->elemcount) return ErrorEXP(7)

*ret=L->base[i-1]//删除位置,这里先返回该值

for(temp=&(L->base[i])temp<=&(L->base[L->elemcount-1])temp++)

*(temp-1)=*temp

L->elemcount--

return OK

}

Status KeyInList(SqPointer L,int i)

{

ElemType temp

time_t t

char tmp[64]

char S

if(!L->base) return ErrorEXP(3)//L不存在，返回

if(i<1 || i>L->elemcount + 1) return ErrorEXP(8)

printf("正在输入第%d个元素的值:",i)

printf("\n编号:(int)\n")

scanf("%d",&temp.NO)

printf("\n姓名:(char *)\n")

scanf("%s",&temp.Name)

printf("\n性别:(m or f)\n")

do{

S=getch()

if(S=='m')

temp.Sex=male

else if(S=='f')

temp.Sex=female

else

puts("Key in 'm' or 'f'.\n")

}while(S!='m' &&S!='f')

putchar(S)

printf("\n年龄:(int)\n")

scanf("%d",&temp.Age)

printf("\n电话:(char *)\n")

scanf("%s",&temp.Tel)

printf("\n记录时间:\n")

t=time(0)

strftime(tmp,sizeof(tmp),"%Y/%m/%d %X %A 本年第%j天 %z",localtime(&t))

puts(tmp)

strcpy(temp.Inserttime,tmp)

if(ListInsert(L,i,temp)==OK)

return OK

else

return ErrorEXP(9)

}

ElemType ScanfElem()

{

ElemType temp

time_t t

char tmp[64]

char S

printf("正在录入元素:")

printf("\n编号:(int)\n")

scanf("%d",&temp.NO)

printf("\n姓名:(char *)\n")

scanf("%s",&temp.Name)

printf("\n性别:(m or f)\n")

do{

S=getch()

if(S=='m')

temp.Sex=male

else if(S=='f')

temp.Sex=female

else

puts("Key in 'm' or 'f'.\n")

}while(S!='m' &&S!='f')

putchar(S)

printf("\n年龄:(int)\n")

scanf("%d",&temp.Age)

printf("\n电话:(char *)\n")

scanf("%s",&temp.Tel)

printf("\n记录时间:\n")

t=time(0)

strftime(tmp,sizeof(tmp),"%Y/%m/%d %X %A 本年第%j天 %z",localtime(&t))

puts(tmp)

strcpy(temp.Inserttime,tmp)

return temp

}

Status ScanfList(SqPointer L,int i)

{

char p='c'

while(putchar('\n'),p=='c'||p=='C')

{ p='\0'

if(KeyInList(L,i++)==ERROR) return ErrorEXP(10)

printf("\nPress ESC key to exit or 'C' to continue...")

while(p!='c' &&p!='C' &&(int)p!=27)

p=getch()

}

return OK

}

Status PrintListProperty(SqPointer L)

{

puts("SqList L Property:")

if(!L->base)

{ puts("链表不存在!")

return OK}

else

puts("链表已初始化...\n")

printf("%d/%d BASE=%d,MemoryStatus=%d\n",L->elemcount,L->length,L->base,L->listsize)

return OK

}

Status PrintOnScreen(SqPointer L)

{

int i

char Stmp[7],t

if(!L->base) return ErrorEXP(3)//L不存在，返回

puts("Push 'C' shell CLS or other key to skip.")

t=getch()

if(t=='c' || t=='C')

system("cls")

puts("数据表打印：")

for(i=0i<=L->elemcount-1i++)

{ printf("\nElem %d st:\n",i+1)

if(L->base[i].Sex == male)

strcpy(Stmp,"male")

else if(L->base[i].Sex == female)

strcpy(Stmp,"female")

else

strcpy(Stmp,"Unknow")

printf("NO:%d\tName:%s\t\tSex:%s\tAge:%d\n\tTel:%s\n\tInsertTime:%s\n",L->base[i].NO,L->base[i].Name,Stmp,L->base[i].Age,L->base[i].Tel,L->base[i].Inserttime)

}

return OK

}

Status PrintElem(ElemPointer elem)

{

char Stmp[7]

printf("\nPrintElem:\n")

if(elem->Sex == male)

strcpy(Stmp,"male")

else if(elem->Sex == female)

strcpy(Stmp,"female")

else

strcpy(Stmp,"Unknow")

printf("NO:%d\tName:%s\t\tSex:%s\tAge:%d\n\tTel:%s\n\tInsertTime:%s\n",elem->NO,elem->Name,Stmp,elem->Age,elem->Tel,elem->Inserttime)

return OK

}

void main() //把以上所有函数都串了起来

{

SqList TheList

SqPointer ListP

ElemType mylistelem,*elemtemp

ElemPointer mylist

int i

char nameT[20]

elemtemp=&mylistelem//*ret

ListP=&TheList

if(InitList(ListP)==OK) puts("InitList(TheList)==OK")

PrintListProperty(ListP)

if(ListEmpty(ListP)==TRUE) puts("ListEmpty==True")

else puts("ListEmpty==False")

ScanfList(ListP,1)

PrintListProperty(ListP)

PrintOnScreen(ListP)

printf("ListElemCount return %d.",ListElemCount(ListP))

puts("\nGetElem index? ")

scanf("%d",&i)

if(GetElem(ListP,i,elemtemp)==OK) PrintElem(elemtemp)

puts("\nLocateElem name? ")

scanf("%s",nameT)

printf("LocateElem return %d.",LocateElem(ListP,nameT))

puts("\nListDelete index? ")

scanf("%d",&i)

if(ListDelete(ListP,i,elemtemp)==OK) PrintElem(elemtemp)

puts("\nListInsert index? ")

scanf("%d",&i)

puts("\nListInsert NEWELEM? ")

ListInsert(ListP,i,ScanfElem())

PrintListProperty(ListP)

PrintOnScreen(ListP)

if(ClearList(ListP)==OK) puts("ClearList==OK")

if(ListEmpty(ListP)==TRUE) puts("ListEmpty==True")

if(DestroyList(ListP)==OK) puts("DestroyList==OK")

getch()

}

/* 函数列表

类型 名称 参数 说明

int ErrorEXP (int i) 错误描述符

Status InitList (SqPointer L) 初始化SqPointer L... 通过L返回base

Status IncreaseList (SqPointer L) L当前满时，继续申请空间

Status DestroyList (SqPointer L) 销毁L

Status ClearList (SqPointer L) 把L置为空表

Boolen ListEmpty (SqPointer L) 判断L是否为空表，是则返回TRUE

int ListElemCount (SqPointer L) 返回当前L中记录的元素个数

Status GetElem (SqPointer L,int i,ElemType *ret) 通过*ret返回i号元素

int LocateElem (SqPointer L,char Locatename[]) 顺序查找表，根据name字段，返回首个匹配元素的i，无则返回0

Status ListInsert (SqPointer L,int i,ElemType newelem) 在L中的i号位置插入newelem元素

Status ListDelete (SqPointer L,int i,ElemType *ret) 删除L中第i号元素，并用*ret返回该元素

Status KeyInList (SqPointer L,int i) 从键盘输入单个元素并插入到i号位置

ElemType ScanfElem () 从键盘输入单个元素返回一个ElemType类型的节点

Status ScanfList (SqPointer L,int i) 从i号开始递增顺序录入元素到L，直到按'ESC'

Status PrintListProperty(SqPointer L) 打印L的属性，打印格式为（已用空间/已申请空间 基址 内存占用）

Status PrintOnScreen (SqPointer L) 打印整张L表到屏幕

Status PrintElem (ElemPointer elem) 打印单个ElemType类型的元素

时间仓促，所以乱了些，书上2章开头 动态线性的顺序表 的基本 *** 作几乎都写了

不知你说的是不是这个，mian函数比较乱，只是把所有的基本 *** 作都串了起来，你

可以根据情况改改主函数的调用过程，就会比较清楚是怎么实现的了。你可以按F10

进行单部跟踪，F11可以进入调用过程，一步一步跟着程序走一遍就好了。

关于动态链表的我之前写过一个，也好象给你看过，这里再附上一起发过去。文件LinkList.c

只实现了构造链表，并打印出来的功能。

*/

#include"stdio.h"

#include"malloc.h"

#include"iostream.h"

typedef int status

typedef int elementype

#define INITSIZE 100

#define INCREMENT 2

struct sqlist

{

elementype *elem

int length

int listsize

}

//建立链表，并排列数据

status listinit(sqlist &l)

{

int i=0,x,j,t

l.elem=(elementype *)malloc(INITSIZE*sizeof(elementype))

if(!l.elem)

{

cout<<"建表失败"<<endl

return 0

}

l.length=0

l.listsize=INITSIZE

while(1)

{

cout<<"请输入数据(输入0时结束):"

cin>>x

if(x==0) break

l.elem[i]=x

++l.length

i++

}

for(i=0i<l.length-1i++)

for(j=0j<l.length-i-1j++)

if(l.elem[j]>l.elem[j+1])

{

t=l.elem[j+1]

l.elem[j+1]=l.elem[j]

l.elem[j]=t

}

cout<<"排序成功"<<endl

return 1

}

//插入数据

status listinsert(sqlist &l,int i,elementype e)

{

elementype *p,*q,*newbase

if(i<1||i>l.length)

{

cout<<"i输入错误"<<endl

return 0

}

if(l.length>=l.listsize)

{

newbase=(elementype*)realloc(l.elem,(l.listsize+INCREMENT)*sizeof(elementype))

if(!newbase)

{

cout<<"申请空间失败"<<endl

return 0

}

l.elem=newbase

l.listsize=l.listsize+INCREMENT

}

q=&(l.elem[i-1])

for(p=&(l.elem[l.length-1])p>=q--p)

{

*(p+1)=*p

}

*q=e

++l.length

cout<<"插入成功"

return 1

}

//删除数据

status listdelete(sqlist &l,int i,elementype &e)

{

elementype *p,*q

if(i<1||i>l.length)

{

cout<<"i输入错误"<<endl

return 0

}

p=&(l.elem[i-1])

e=*p

q=l.elem+l.length-1

for(++pp<=q++p)

{

*(p-1)=*p

}

--l.length

cout<<"删除成功"<<endl

free(&e)

return 1

}

//删除重复的数据

status listdeleterepeat(sqlist &l)

{

int i,j

elementype *p,*q,e

for(i=0i<l.length-1i++)

for(j=i+1j<l.length-1j++)

if(l.elem[i]==l.elem[j])

{

p=&(l.elem[j])

e=*p

q=l.elem+l.length-1

for(++pp<=q++p)

{

*(p-1)=*p

}

--l.length

free(&e)

j--

}

return 1

}

//输出顺序表数据

status displaylist(sqlist &l)

{

int i

cout<<"顺序表的数据为:"<<endl

for(i=0i<l.lengthi++)

{

cout<<l.elem[i]<<" "

}

cout<<endl

return 1

}

//查找数据

status locatelem(sqlist &l,int x)

{

elementype *p

int i=1

p=l.elem

while(i<l.length&&(*p++)!=x)

i++

cout<<i<<endl

return 1

}

//清空列表

void listclear(sqlist &l)

{

l.length=0

}

//销毁顺序表

void listdestroy(sqlist &l)

{

if(l.elem)

free(l.elem)

}

//求顺序表长度

status listlength(sqlist &l)

{

cout<<"顺序表的长度为:"<<l.length<<endl

return 1

}

int main()

{

sqlist l

int a,i,x

elementype e

cout<<"*************************************************"<<endl

cout<<"* 顺序表的表示和实现 *"<<endl

cout<<"*************************************************"<<endl

do{

cout<<"*************************************************"<<endl

cout<<"* 菜单 *"<<endl

cout<<"* 1.建立顺序表 *"<<endl

cout<<"* 2.插入数据*"<<endl

cout<<"* 3.删除数据*"<<endl

cout<<"* 4.删除重复数据*"<<endl

cout<<"* 5.清空数据*"<<endl

cout<<"* 6.查找数据*"<<endl

cout<<"* 7.顺序表的长度*"<<endl

cout<<"* 8.显示顺序表 *"<<endl

cout<<"* 0.退出顺序表 *"<<endl

cout<<"*************************************************"<<endl

cout<<"输入你的选择:"

cin>>a

switch(a)

{

case 1: listinit(l)

displaylist(l)

break

case 2: cout<<"请输入要插入数据的位置:"

cin>>i

cout<<"请输入要插入的数据元素:"

cin>>e

listinsert(l,i,e)

displaylist(l)

break

case 3: cout<<"请输入要删除的数据的位置:"

cin>>i

listdelete(l,i,e)

displaylist(l)

break

case 4: cout<<"删除前的数据为:"

displaylist(l)

listdeleterepeat(l)

cout<<"删除后的数据为:"

displaylist(l)

break

case 5: cout<<"清空前为:"

displaylist(l)

cout<<"清空后为:"

listclear(l)

displaylist(l)

break

case 6: cout<<"输入你要查找的数据:"

cin>>x

cout<<"你要查找的数据的位置为:"

locatelem(l,x)

displaylist(l)

break

case 7: cout<<"顺序表的长度为:"

listlength(l)

break

case 8: displaylist(l)

break

default: break

}

}while(a!=0)

return 1

}

---