定义单链表【急急急急急】

Question

定义一个单链表L，其数据元素类型为int型，首先用头插法建立该单链表，并插入一个数据元素，然后显示输出该链表（元素值自定）。再尝试进行如下操作：求该链表的长度；查找该链表的某个值x；删除某个节点x。

Answer 1

这个是我给我同学写的一个单链表，写的比较简单，刚开始学的时候可以看看。

写法不是很严谨，主要目的是方便看懂，学会单链表是一个什么样的概念。

#include <stdio.h>
#include <malloc.h>//malloc函数所需要的头文件
struct biao
{
   int data;  //用来存储数据，不一定是int 类型的，这个你要看你实际的需要
   struct biao *next;//用来存储地址，就是告诉下一个元素的位置
};
void input_data(struct biao *head)//这个函数的功能就是将数据存入链表
{
   int n,i;
   scanf("%d",&n);//你有多少个数据元素要录入链表
   for(i=1; i<=n; i++)//这个循环就是在录入数据
   {
      //在内存中，开辟一个空间，用来存放数据元素
      struct biao *temp = (struct biao *)malloc(sizeof(struct biao));
      scanf("%d",&(temp->data));//输入数据元素
      head->next = temp;
      head = temp;
   }
   head->next = NULL;
}

void output_data(struct biao *head)//将数据输出
{
   head = head->next;//现在是第一个元素
   while(head)//判断有没有结束，没有的话，就将数据输出
   {
      printf("%d ",head->data);
      head = head->next;//这个就是改变头指针是谁，就是说，现在该轮到谁传话了
   }
   printf("\n\n");//空行,没什么意思，就是方便察看，类似美观，也可以不要
}

void cha_ru(struct biao *head)//删除数据元素
{
   int wei_zhi,i;
   scanf("%d",&wei_zhi);
   head = head->next;//这里已经偏移了一次，所以下面是-2，不是-1
   for(i=1; i<=wei_zhi-2; i++)//当你要知道第N个同学传话的内容，应该去找第N-1位同学
      head = head->next;
   struct biao *temp = (struct biao *)malloc(sizeof(struct biao));
   scanf("%d",&(temp->data));//输入数据元素
   temp->next = head->next;
   head->next = temp;
}

void shan_shu(struct biao *head)//删除数据元素
{
   int wei_zhi,i;
   scanf("%d",&wei_zhi);//要删除第几个元素
   head = head->next;
   for(i=1; i<=wei_zhi-2; i++)
      head = head->next;         //这个注释是给下面的注释做辅助说明用的。 N-1，N，N+1
   head->next = head->next->next;//删除第N个的时候，就只要把N+1的地址告诉给N-1就行
}
int main(void)
{
   struct biao *head = (struct biao *)malloc(sizeof(struct biao));
   //上面是定义了一个结构体类型的指针，然后动态分配一个地址，并让这个指针指向该地址
   //malloc这个函数是一个动态分配内存的一个函数

   input_data(head);//录入数据
   output_data(head);//输出数据

   cha_ru(head);//插入数据
   output_data(head);//输出数据

   shan_shu(head);//删除数据
   output_data(head);//输出数据

   return 0;
}

     下面是顺序表的，写了一个简单的界面。

　　更多的内容可以去看别人的博客（下面图片的水印是我博客的地址）。

/************************************************************
   说明：
         1、主函数内的代码是为了测试方便，可以自行修改。
         2、宏定义NEWS是人机交互信息提示，若不需要，可修改为0。
         3、若是windows系统，请将258行中的 clear 修改为 cls。
         4、在输入数据后，请多按一下回车，实现清屏。
   环境：ubuntu12.04LTS、codeblocks10.05、2014-04-02
************************************************************/
#include <iostream>
#include <stdlib.h>
#include <malloc.h>
#include <cstring>
#define NEWS 1
#define LIST_INIT_SIZE 100
#define LIST_ADD_SIZE 10
#define NEW_SIZE (L->list_size + LIST_ADD_SIZE)
using namespace std;
typedef int Elem_Type;
typedef struct
{
   Elem_Type *data;//元素
   int len;       //长度
   int list_size; //空间
}Sq_List;
typedef enum
{
   OK    = 0,      //正常
   ERROR = -1,     //逻辑异常
   OVER  = -2      //内存异常
}Status;
/******************************
   函数名：Init_List
   功  能：构造、初始化线性表
******************************/
Sq_List *Init_List(void)
{
   Sq_List *L = (Sq_List *)malloc(sizeof(Sq_List));
   if(!L)
     exit(OVER);
   L->data = (Elem_Type *)malloc(LIST_INIT_SIZE*sizeof(Elem_Type));
   if(!L->data)
     exit(OVER);
   L->len = 0;
   L->list_size = LIST_INIT_SIZE;
   #if(NEWS)
      cout<<"构造成功，已初始化"<<endl;
   #endif
   return L;
}
/******************************
   函数名：Destroy_List
   功  能：销毁线性表
******************************/
Status Destroy_List(Sq_List *L)
{
   free(L);
   #if(NEWS)
      cout<<"销毁成功，请不要再使用"<<endl;
   #endif
   return OK;
}
/******************************
   函数名：Clear_List
   功  能：清空线性表
******************************/
Status Clear_List(Sq_List *L)
{
   memset(L->data,-1,sizeof(L->data));
   L->len = 0;
   #if(NEWS)
      cout<<"已全部清空"<<endl;
   #endif
   return OK;
}
/******************************
   函数名：Empty_List
   功  能：判断线性表是否为空
******************************/
bool Empty_List(Sq_List *L)
{
   return L->len == 0;
}
/******************************
   函数名：Length_List
   功  能：获取线性表长度
******************************/
int Length_List(Sq_List *L)
{
   return L->len;
}
/******************************
   函数名：Get_Elem_List
   功  能：指定位置获取元素
******************************/
Status Get_Elem_List(Sq_List *L, int index, Elem_Type *e)
{
   if( !(1 <= index && index <= Length_List(L)) )
     #if(NEWS)
      {
         cout<<"获取位置不合法"<<endl
             <<"下面显示的数据是上次输入的num的值,请注意！！！"<<endl;
         return ERROR;
      }
     #else
        return ERROR;
     #endif
   *e = L->data[index-1];
   return OK;
}
/******************************
   函数名：Insert_List
   功  能：指定位置插入元素
******************************/
Status Insert_List(Sq_List *L, int index, Elem_Type e)
{
   if( !(1 <= index && index <= Length_List(L)+1) )
     #if(NEWS)
      {
         cout<<"插入位置不合法"<<endl;
         return ERROR;
      }
     #else
        return ERROR;
     #endif
   if( Length_List(L) >= L->list_size)
     #if(NEWS)
      cout<<"刚才增加了存储空间"<<endl;
     #endif
     L->data = (Elem_Type *)realloc(L->data, NEW_SIZE*sizeof(Elem_Type));
   if(!L->data)
     exit(OVER);

   L->list_size += LIST_ADD_SIZE;

   for(int i=Length_List(L); i >= index-1; i--)
      L->data[i+1] = L->data[i];

   L->data[index-1] = e;
   L->len++;
   #if(NEWS)
      cout<<"插入成功"<<endl;
   #endif
   return OK;
}
/******************************
   函数名：Delete_List
   功  能：指定位置删除元素
******************************/
Status Delete_List(Sq_List *L, int index, Elem_Type *e)
{
   if( Empty_List(L) || !(1 <= index && index <= Length_List(L)) )
     #if(NEWS)
      {
         cout<<"删除位置不合法 or 目前是空表"<<endl;
         return ERROR;
      }
     #else
        return ERROR;
     #endif
   *e = L->data[index -1];
   for(int i=index; i<Length_List(L); i++)
      L->data[i-1] = L->data[i];
   #if(NEWS)
      cout<<"删除成功"<<endl;
   #endif
   L->len--;
   return OK;
}
/******************************
   函数名：Print_List
   功  能：输出所有元素
******************************/
Status Print_List(Sq_List *L)
{
   if( Empty_List(L) )
     return ERROR;
   int temp;
   for(int i=1; i<=Length_List(L); i++)
   {
      Get_Elem_List(L,i,&temp);
      cout<<temp<<" ";
   }
   cout<<endl;
   return OK;
}
/******************************
   函数名：print_news
   功  能：方便用户选择
******************************/
void print_news(void)
{
   cout<<"\n\n\n\t\t********************"
    <<"*****************************"<<endl
    <<"\t\t*\t\t0 建立、初始化\t\t\t*"<<endl
    <<"\t\t*\t\t\t\t\t\t*"<<endl
    <<"\t\t*\t\t1 插入元素\t\t\t*"<<endl
    <<"\t\t*\t\t\t\t\t\t*"<<endl
    <<"\t\t*\t\t2 删除元素\t\t\t*"<<endl
    <<"\t\t*\t\t\t\t\t\t*"<<endl
    <<"\t\t*\t\t3 销毁  \t\t\t*"<<endl
    <<"\t\t*\t\t\t\t\t\t*"<<endl
    <<"\t\t*\t\t4 获取表长\t\t\t*"<<endl
    <<"\t\t*\t\t\t\t\t\t*"<<endl
    <<"\t\t*\t\t5 清空  \t\t\t*"<<endl
    <<"\t\t*\t\t\t\t\t\t*"<<endl
    <<"\t\t*\t\t6 获取元素\t\t\t*"<<endl
    <<"\t\t*\t\t\t\t\t\t*"<<endl
    <<"\t\t*\t\t7 打印    \t\t\t*"<<endl
    <<"\t\t*\t\t\t\t\t\t*"<<endl
    <<"\t\t*\t\t8 退出  程序\t\t\t*"<<endl
    <<"\t\t********************"
    <<"*****************************"<<endl;
}
int main(void)
{
   Sq_List *test = NULL;
   while(true)
   {
      print_news();
      int choose,index,num;
      cout<<"要进行什么操作？"<<endl;
      cin>>choose;
      switch(choose)
      {
         case 0:
            test = Init_List();break;
         case 1:
            cout<<"插入位置 "<<endl;
            cin>>index;
            cout<<"插入数据 "<<endl;
            cin>>num;
            Insert_List(test,index,num);break;
         case 2:
            cout<<"删除的位置"<<endl;
            cin>>index;
            Delete_List(test,index,&num);
            cout<<"被删除的元素是："<<num<<endl;break;
         case 3:
            Destroy_List(test);break;
         case 4:
            cout<<Length_List(test)<<endl;break;
         case 5:
            Clear_List(test);break;
         case 6:
            cout<<"获取哪个位置的元素"<<endl;
            cin>>index;
            Get_Elem_List(test,index,&num);
            cout<<num<<endl;break;
         case 7:
            Print_List(test);break;
         case 8:
            return 0;
         default:
            break;
      }
      getchar();
      getchar();
      system("clear");
   }
   return 0;
}