数据结构代码：单链表的建立插入和删除

红太狼 2023-07-12 06:21 31阅读 0赞

数据结构代码：单链表的建立插入和删除

# include<stdio.h>
    # include<malloc.h>
    # include<stdlib.h>
    # define TRUE 1
    # define FALSE 0
    # define OK 1
    # define ERROR 0
    # define INFEASIBLE -1
    # define OVERFLOW -2
    # define LIST_INIT_SIZE 100
    # define LISTINCREMENT 10
    
    typedef int Status;
    typedef int ElemType;
    
    typedef struct { 
    	ElemType * elem;
    	int length;
    	int listsize;
    }SqList;
    
    Status InitList_Sq(SqList &L){ 
    	int elem;
    	L.elem = (ElemType*) malloc(LIST_INIT_SIZE * sizeof(ElemType));
    	if (! L.elem)exit(OVERFLOW);
    	L.elem[0] = 201806016;
    	L.elem[1] = 201806006;
    	L.elem[2] = 201806026;
    	L.elem[3] = 201806066;
    	L.length = 4;
    	L.listsize = LIST_INIT_SIZE;
    	return OK;
    }//InitList_Sq
    
    Status ListInsert_Sq(SqList &L,int i,ElemType e){ 
    	ElemType *p,*q,*newbase;
    	if (i < 1 || i > L.length + 1 )
    	  return ERROR;
    	if (L.length >= L.listsize)
    	{ 
    		newbase = (ElemType * )realloc(L.elem,(L.listsize + LISTINCREMENT) * sizeof(ElemType));
    		if (! newbase)exit(OVERFLOW);
    		L.elem = newbase;
    		L.listsize += LISTINCREMENT;
    	}
    	q = & (L.elem[i-1]);
    	for (p = & (L.elem[L.length - 1]);p >= q;--p)
    		* (p+1) = *p;
    	*q = e;
    	++L.length;
    	return OK;
    }//ListInsert_Sq
    
    Status LIstDelete_Sq(SqList &L,int i,ElemType &e){ 
    	ElemType *p,*q;
    	if ((i < 1) || (i > L.length) ) return ERROR;
        p = & (L.elem[i-1]);
    	e = *p;
    	q = L.elem + L.length - 1;
    	for (++p;p <= q;++ p)
    		* (p-1) = * p;
    	-- L.length;
    	return OK;
    }//ListDelete_Sq
    
    typedef struct LNode
    { 
    	ElemType data;
    	struct LNode *next;
    }LNode,*LinkList;
    
    LinkList CreateList_L(LinkList &L,int n){ 
    	LinkList p,s;
    	int i;
    	p = L = (LinkList)malloc(sizeof(LNode));
    	printf("请输入单链表中的元素：\n");
    	for(i=n;i>1;--i){ 
    		s = (LinkList)malloc(sizeof(LNode));
    		scanf("%d",&s->data);
    		p->next = s;
    		p = s;
    	}
    	p -> next = NULL;
    	return L;
    }//尾插法创建链表
    
    LinkList ListInsert_L(LinkList &L,int i,ElemType e){ 
    	//在带头结点的单链线性表L中第i个位置之前插入元素e 
    	LinkList p,s;
    	p=L;
    	int	j=0;
    	while(p&&j<i-1){ 
    		p=p->next;
    		j++;
    	}
    	if(!p&&j>i-1)
    		return 0;
    	s=(LinkList)malloc(sizeof(LNode));
    	s->data=e;
    	s->next=p->next;
    	p->next=s;
    	return L;
    }//ListInsert_L
     
    Status ListDelete_L(LinkList &L,int i,ElemType &e){ 
    	//在带头结点的单链线性表L中，删除第i个元素，并由e返回其值 
    	LinkList p,s,q; 
    	p=L;
    	int j=0;
    	while(p -> next && j < i-1){ 
    		p = p -> next;
    		++j;
    	}
    	if(!p&&j>i-1) return ERROR;
    	q=p->next;
    	p->next=q->next;
    	e=q->data;
    	free(q);
    	return e;
    }//ListDelete_L 
    
    void PrintList(LinkList &L){ 
    	LinkList p;
    	p=L->next;
    	printf("此时单链表中的元素为；\n");
    	while(p){ 
    		printf("%5d",p->data);
    		p=p->next;
    	}
    }//输出链表元素 
    
    main(){ 
    	LinkList L,p;
    	int a,d,c,e;
    	ElemType b;
    	printf("请先建立链表\n");
    	printf("请输入单链表的元素个数\n");
    	scanf("%d",&d);
    	p = CreateList_L(L,d);
    	
    	printf("请输入要插入的位置与要插入的元素\n");
    	scanf("%d %d",&a,&b); 
    	ListInsert_L(L,a,b);
    	PrintList(L);
    	printf("\n");
    	
    	printf("请输入要删除的位置\n");
    	scanf("%d",&c);	
    	ListDelete_L(L,c,e);
    	PrintList(L);
    	printf("\n");
    }

运行环境：DEVC++  
用了太多\#define和typedef 好像有些没有必要  
程序与严薇敏《数据结构（C语言版）》一样