线性表及其应用

输出结果：

iuput the the length of List:7

input the List:

21 23 14 5 56 17 31

iuput the insert location:3

iuput the insert number:68

input the List:the new List's length is：8

the new List's data is:

21 23 14 68 5 56 17 31

1. 建立一个带头结点的单链表，结点的值域为整型数据。要求将用户输入的数据按尾插入法来建立相应单链表。

#include 
#include 
typedef struct k
{int data;struct k* next;
}Node; /*创建链表*/Node* initList()
{ /*初始化*/Node *h=(Node *)malloc(sizeof(Node));h->next=NULL;return h;
}
Node* creatList()
{ /*尾插法创建*/Node *h, *tail,*q;int x;h=(Node *)malloc(sizeof(Node));h->next=NULL;tail=h; /*tail类似于标签*/printf("input nums, endby -1:\n");scanf("%d",&x);while(x!=-1){//1、造结点q，并赋值；q=(Node *)malloc(sizeof(Node));q->data=x;q->next=NULL;//2、将q插入链表；tail->next=q;tail=q;//3、继续读scanf("%d",&x);}return h;
}
void printList(Node *h)
{ /*输出函数*/if(h->next==NULL) return;for(h=h->next;h!=NULL; h=h->next)if(h->next!=NULL)printf("%d->", h->data);elseprintf("%d",h->data);
}
int main()
{
Node *h;
h=creatList();
printf("\n链表为：\n");
printList(h);
}

输出结果为：

input nums, endby -1:

4 8 56 4 3 56 13 5 15 4 -1

链表为：

4->8->56->4->3->56->13->5->15->4

四、思考与提高

1. 如果按由表尾至表头的次序输入数据元素，应如何建立顺序表。

使用头插入法建立链表

2. 在main函数里如果去掉L=&a语句，会出现什么结果？

       无法传递地址

五、完整参考程序

    1.顺序线性表的建立、插入及删除。

#include

#include

#define OK   1

#define ERROR  0

#define ElemType int

#define   MAXSIZE  100          /*此处的宏定义常量表示线性表可能达到的最大长度*/

typedef  struct

{

       ElemType  elem[MAXSIZE];  /*线性表占用的数组空间*/

       int       last;                    /*记录线性表中最后一个元素在数组elem[ ]中的位置（下标值），空表置为-1*/

}SeqList;

void initial(SeqList *v)         //初始化线性表

{//初始化线性表

 int i;

 printf("请输入初始线性表长度：n="); //输入线性表初始化时的长度

 scanf("%d",&v->last);

 printf("请输入从1到%d的各元素\n",v->last);

 getchar();

 for(i=0;ilast;i++) scanf("%d",&v->elem[i]); //输入线性表的各元素

 v->last--;

}

int  InsList(SeqList *L,int i,ElemType e)      //在线性表中插入元素

{

//实验完成该部分的内容

       int k;

       for(k=L->last;k>i-1;k--)

              L->elem[k+1]=L->elem[k];

       L->elem[i-1]=e;

       L->last++;

       return OK;

}

int  DelList(SeqList *L,int i,ElemType *e)    

/*在顺序表L中删除第i个数据元素，并用指针参数e返回其值。i的合法取值为1≤i≤L.last+1 */   

{

       //实验完成该部分的内容

       int k;

       if((i<1)||(i>L->last))

       {

              printf("删除的位置不合法！");

              return ERROR;

       }

       *e=L->elem[i-1];

       for(k=i;klast;k++)

              L->elem[k-1]=L->elem[k];

       L->last--;

       return OK;

}

int  Locate(SeqList L, ElemType e)   

{    

       //实验完成该部分的内容

       int i=0;

       while((i<=L.last)&&L.elem[i]!=e)

              i++;

       if(i<=L.last)

              return(i+1);

       else

              return(-1);

}

void print(SeqList S)

{    

       int i;

       for(i=0;i<=S.last;i++)

              printf("%5d",S.elem[i]);

       printf("\n");

}

void main()

{SeqList S;      //S为一线性表

 int loc,flag=1;

 char j;

 int ch;

 int temp;

printf("本程序用来实现顺序结构的线性表。\n");

 printf("可以实现查找、插入、删除等操作。\n");

 initial(&S);         //初始化线性表

 while(flag)

    { printf("请选择:\n");

      printf("1.显示所有元素\n");

      printf("2.插入一个元素\n");

      printf("3.删除一个元素\n");

      printf("4.查找一个元素\n");

      printf("5.退出程序    \n");

      scanf(" %c",&j);

      switch(j)

       {case '1':print(S); break; //显示所有元素

        case '2':{printf("请输入要插入的元素和插入位置:\n");

                 printf("格式：数据，位置；例如:a,2\n");

                 scanf(" %d,%d",&ch,&loc);  //输入要插入的元素和插入的位置

                 temp=InsList(&S,loc,ch);     //插入

                 if(temp==ERROR)  printf("插入失败!\n");  //插入失败

                   else  {printf("插入成功!\n");   print(S);} //插入成功

                 break;

                }

        case '3':{printf("请输入要删除元素的位置:");

                 scanf("%d",&loc);    //输入要删除的元素的位置

                 temp=DelList(&S,loc,&ch);  //删除

                 if(temp==OK) printf("删除了一个元素:%d\n",ch); //删除成功

                 else printf("该元素不存在!\n");  //删除失败

                 print(S);

                 break;

                }

        case '4':{printf("请输入要查找的元素:");

                 scanf(" %d",&ch);      //输入要查找的元素

                 loc=Locate(S,ch);      //定位

                 if(loc!=-1) printf("该元素所在位置:%d\n",loc); //显示该元素位置

                 else    printf("%c 不存在!\n",ch);//当前元素不存在

                 break;

                }

        default:flag=0;printf("程序结束，按任意键退出!\n");

       }

    }

 getchar();

}

2.链式线性表的建立、插入及删除。

#include

#include

#include

#define OK   1

#define ERROR  0

#define TRUE 1

#define FALSE 0

typedef int ElemType;

typedef struct Node    /*结点类型定义*/

{

       ElemType data;

       struct Node  * next;

}Node, *LinkList;  /* LinkList为结构指针类型*/

void init_linklist(LinkList *l)/*对单链表进行初始化*/

{

       *l=(LinkList)malloc(sizeof(Node)); /*申请结点空间*/

       (*l)->next=NULL;                      /*置为空表*/

}

void CreateFromTail(LinkList L)

{

              //实验完成该部分的内容

Node *r, *s;

   int c;

   int  flag =1; /*设置一个标志，初值为1，当输入-1时，flag为0，建表结束*/

   r=L;                /*r指针动态指向链表的当前表尾，以便于做尾插入，其初值指向头结点*/

    printf("请输入数据，以-1结束:"); //输入生成单链表时的元素

while(flag)         /*循环输入表中元素值，将建立新结点s插入表尾*/

{

  scanf("%d",&c);

  if(c!=-1)

  {

   s=(Node*)malloc(sizeof(Node));

   s->data=c;

   r->next=s;

   r=s;

  }

  else

  {

   flag=0;

   r->next=NULL;   /*将最后一个结点的next链域置为空，表示链表的结束*/

  }

}

}

int InsList(LinkList L,int i,ElemType e)

/*在带头结点的单链表L中第i个位置插入值为e的新结点*/

{ 

//实验完成该部分的内容}

int DelList(LinkList L,int i,ElemType *e)

/*在带头结点的单链表L中删除第i个元素，并将删除的元素保存到变量*e中*/

{ 

//实验完成该部分的内容

Node *pre,*s;

   int k;

   if(i<=0) return ERROR;

   pre=L; k=0;

   while(pre!=NULL&&k

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！