1list.c

数据结构中链表实现得源码,包括链表的插入,删除,出栈进栈

#include <stdio.h>
#include <stdlib.h>
#include <dos.h>
#include <conio.h>
#include <bios.h>
#define OK  1
#define ERROR   0
#define INFWASIBLE -1
#define OVERFLOW    -2
#define LIST_IN_SIZE 100    /*线性表存储空间的初始分配量*/
#define LISTINCREMENT 10    /*线性表存储空间的分配增量*/
typedef struct{
    int *elem;   /*存储数据*/
    int length;     /*当前长度*/
    int listsize;   /*当前分配的存储容量*/
}Sqlist;
Sqlist *L;
int Creat_Sq(Sqlist *p)/*构造一个线性表*/
    {
        int ch;
        int *newbase;
        p->elem=malloc(LIST_IN_SIZE*sizeof(int));
        if(!p->elem)exit(OVERFLOW);/*存储分配失败*/
        p->length=0; /*空表长度为0 */
        p->listsize= LIST_IN_SIZE;   /*初始存储容量*/
        while(1)
        {
            if(p->length>=p->listsize){  /*当前的存储空间已满,增加分配*/
                newbase=realloc(p->elem,(p->listsize+LISTINCREMENT)*sizeof(int));
                if(!newbase)exit(OVERFLOW);  /*存储分配失败*/
                p->elem=newbase; /*新地址 */
                p->listsize+=LISTINCREMENT;  /*增加存储容量*/
            }
            printf("please input the data ;\n");
            scanf("%d",&p->elem[p->length]);
            p->length++;
            printf("\nmore data ?press '1'to continue,but '0' to stop input;\n");
            scanf("%d",&ch);
            if(ch==0)
                break;


        }   /*end of for*/
        getch();
        return p->length;
    }
/*-----------------------Creat_Sq-------------------------------------- */

 int Insert_Sq(Sqlist *sq)    /*在顺序线性表sq中第i位置之前插入新元素*/
{
        int *p,*q;
        int i,e;
        int *newbase;
        printf("input the i\n");
        scanf("%d",&i);
        printf("input the data you want to insert;\n");
        scanf("%d",&e);
        if(i<1||i>=sq->length+1)return ERROR;/*i值不合法*/
        if(sq->length>=sq->listsize){  /*当前的存储空间已满,增加分配*/
                newbase=(int *)realloc(sq->elem,(sq->listsize+LISTINCREMENT)*sizeof(int));
                if(!newbase)exit(OVERFLOW);  /*存储分配失败*/
                sq->elem=newbase; /*新地址*/
                sq->listsize+=LISTINCREMENT;  /*增加存储容量*/
            }  /*of*/
        q=&(sq->elem[i-1]);   /*q为插入位置 */
        for(p=&(sq->elem[sq->length-1]);p>=q;--p)*(p+1)=*p;/*插入位置以及之后的元素后移*/
        *q=e;   /*  插入e */
        ++sq->length; /*表长加1*/
        printf("\nthe data has been inserted!");
        getch();
        return OK;
    }
/*-----------------------------Insert_Sq---------------------------------- */

int Delete_Sq(Sqlist *sq)    /*在顺序线性表L中删除第i位置元素,并用e返回其值*/
{
    int *p,*q;
    int i,e;
    printf("input the i\n");
    scanf("%d",&i);;
    if((i<1)||(i>sq->length))return ERROR;/*i值不合法*/
    p=&(sq->elem[i-1]);   /*p为被删除元素的位置*/
    e=*p;/*被删除元素的值负值给e*/
    q=sq->elem+sq->length-1;/*表尾元素的位置*/
    for(++p;p<=q;++q)*(p-1)=*p;/*被删元素之后的元素左移*/
    --sq->length;
    printf("the deleted data is %d\n",e);
    getch();
    return e;
}
/*----------------------Delete_Sq------------------------------*/

int Longth_Sq(Sqlist *sq)/*求线性表的长度*/
{
    if(!sq) return ERROR;
    printf("the length of the list is %d\n",sq->length);
    getch();
    return OK;

}
/*----------------------Length_Sq----------------------------------*/

int Clear_Sq(Sqlist *sq) /*清空线性表*/
{
    sq->elem=(int *)malloc(LIST_IN_SIZE*sizeof(int));
    if(!sq->elem)exit(OVERFLOW);/*存储分配失败*/
    sq->length=0; /*空表长度为0*/
    sq->listsize= LIST_IN_SIZE;   /*初始存储容量*/
    printf("the list has been cleared!\npress any key to return! \n");
    getch();
    return OK;
}/*----------------------------Clear_Sq-----------------------------*/
int Display(Sqlist *sq)/*显示所有元素*/
{
    int i;
    for(i=0;i<sq->length;i++)
    {
        printf("%d\t",sq->elem[i]);
    }
    printf("\npress any key to return!\n");
    getch();
    return OK;
}
/*-----------------------------Display(SqList &L)----------------*/

void Save_Sq(Sqlist *p)
{
    FILE *fp;
    char fname[20];
    
    if(p==NULL)
    {   clrscr();
        printf("There is no list for save!exit");
        getch();
        return;
    }
    
    printf("please input the file name you want to save :\n");
    scanf("%s",fname);
    
    if((fp=fopen(fname,"wb"))==NULL)
    {
        printf("Can not save the file!\n");
        return;
    }
    
    printf("\nsaving file...\n");
    fwrite(p,sizeof(Sqlist),1,fp);
    fclose(fp);
    printf("the list have been saved in the file ,press any key to  contune.\n");
    getch();
}
/*---------------------------save_Sq-------------------------*/



Sqlist **loadsq(void)
{   
    FILE *fp;
    Sqlist *sq;
    int *newbase;
    char fname[20];
    printf("Please input the file name you want to load:\n");
    scanf("%s",fname);
    if((fp=fopen(fname,"rb"))==NULL)
    {
        printf("Can not open the file!Pleade choose again!\n");
        getch();
        return NULL;
    }

    printf("\nloading...\n");

    sq=malloc(sizeof(Sqlist));
    if(!sq)exit(OVERFLOW);/*存储分配失败*/
    sq->elem=malloc(LIST_IN_SIZE*sizeof(int));
    if(!sq->elem)exit(OVERFLOW);/*存储分配失败*/
    sq->length=0; /*空表长度为0 */
    sq->listsize= LIST_IN_SIZE;   /*初始存储容量*/
    while(!feof(fp))
    {
        if(1!=fread(sq,sizeof(Sqlist),1,fp)){
        if(sq->length>=sq->listsize){  /*当前的存储空间已满,增加分配*/
            newbase=realloc(sq->elem,(sq->listsize+LISTINCREMENT)*sizeof(int));
            if(!newbase)exit(OVERFLOW);  /*存储分配失败*/
            sq->elem=newbase; /*新地址 */
            sq->listsize+=LISTINCREMENT;  /*增加存储容量*/
            }
            break;
        }

    }
    fclose(fp);
    printf("the list has been load,press any key to return!\n");
    getch();
    return(sq);

}
/*-----------------------------load----------------------------*/
void mainmenu()
{
    window(1,1,80,25);
    clrscr();
    printf("Create a list --1!\r\n");
    cprintf("Clear the list --2!\r\n");
    cprintf("The length of list --3!\r\n");
    cprintf("Insert a data --4!\r\n");
    cprintf("Delete a data --5!\r\n");
    cprintf("Display the list --6!\r\n");
    cprintf("Save the list --7!\r\n");
    cprintf("Load the list --8!\r\n");
    cprintf("-----------------Choose the operation with the number----------\r\n");
    cprintf("---------------------------press 0 to exit !-------------------\r\n");
}
void main()
{
    int a;
    L=(Sqlist *)malloc(sizeof(Sqlist));
    mainmenu();
    scanf("%d",&a);
    clrscr();
    while(a!=0)
    {

        switch(a)
        {
            case 1:Creat_Sq(L);printf("\ncreate over!\n");getch();mainmenu();break;
            case 2:Clear_Sq(L);mainmenu();break;
            case 3:Longth_Sq(L);mainmenu();break;
            case 4:Insert_Sq(L);mainmenu();break;
            case 5:Delete_Sq(L);mainmenu();break;
            case 6:Display(L);mainmenu();break;
            case 7:Save_Sq(L);mainmenu();break;
            case 8:L=loadsq();mainmenu();break;
            default:break;
        }
        scanf("%d",&a);
        clrscr();
    }
}