网站 › 『编程语言区』 › [笔记]一线性表

沧浪之水濯我心 发表于 2018-6-8 22:04

[笔记]一线性表

本帖最后由 wushaominkk 于 2018-6-9 21:13 编辑

初学者，在前人基础上简单修改一下，作为自己的学习笔记。
这段代码是严蔚敏书数据结构2.1内容，希望能给其他初学者带来帮助！

第一次上传其实是有些不合理的代码的，但没想到有好几位朋友回复，要学习收藏，甚感惭愧，于是重新写了一遍，加了注释，经过调试，修改了不合理的代码，谢谢！
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#include<string.h>
#include<Windows.h>
#include<time.h>

#define TRUE 1      //是
#define FALSE 0   //否
#define OK 1            //完成
#define ERROR 0            //错误
#define Warnning 0//警告
#define FAILED 0    //失败
#define OVERFLOW -2 //内存溢出
/* 上述7个变量本质都一样，只是取个名字方便理解 */

#define LIST_INIT_SIZE 10          //分配大小

typedef int Order;                        //排序方式
typedef int Status;                  //完成状态
typedef int ElemType;                //代表元素
/*上述三个都是int类型，取个别名方便理解*/

typedef struct
{
      ElemType *Elem;
      int Length;
      int ListSize;
}pList;

Status InitList(pList *L)      
{      //初始化线性表
      // 操作结果：构造一个空的顺序线性表L
      L->Elem=(ElemType *)malloc(sizeof(ElemType)*LIST_INIT_SIZE);
      if(!L->Elem)
      {
                printf("内存分配请求失败，你脸真的是太黑了！\n");
                exit(OVERFLOW);// 存储分配失败
      }
      L->Length=0;                                        // 空表长度为0
      L->ListSize=LIST_INIT_SIZE;                // 初始存储容量
      printf("线性表初始化成功！\n");
      return OK;
}

void DestroyList(pList *L)
{      // 初始条件：顺序线性表L已存在。操作结果：销毁顺序线性表L
      if(L->Elem)
      {      
                free(L->Elem);
                L->Elem=NULL;
                L->Length=NULL;
                L->ListSize=NULL;
                printf("线性表销毁成功！\n");
      }
}

void ClearList(pList *L)
{      // 初始条件：顺序线性表L已存在。操作结果：将L重置为空表
      L->Length=0;
      printf("线性表置空成功！\n");
}

Status ListEmpty(pList *L)
{      // 初始条件：顺序线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE
      if(L->Length)
                return TRUE;
      else
                return FALSE;
}

Status ListLength(pList *L)
{      // 初始条件：顺序线性表L已存在。操作结果：返回L中数据元素个数
      return L->Length;
}

ElemType GetElem(pList *L,int i,ElemType *e)
{      // 初始条件：顺序线性表L已存在,1≤i≤ListLength(L)。操作结果：用e返回L中第i个数据元素的值
      int Len=ListLength(L);
      if(i < 1 || i > Len)
      {
                printf("当前线性表范围为%d，输入范围不在此范围中！\n",Len);
                return Warnning;
      }
      *e=L->Elem;
      return *e;
}

int LocateElem(pList *L,ElemType e,Status(*compare)(ElemType,ElemType))
{ // 初始条件：顺序线性表L已存在，compare()是数据元素判定函数(满足为1，否则为0)
   // 操作结果：返回L中第1个与e满足关系compare()的数据元素的位序。
   //         若这样的数据元素不存在，则返回值为0。算法2.6
   ElemType *p;
   int i=1; // i的初值为第1个元素的位序
   p=L->Elem; // p的初值为第1个元素的存储位置
   while(i <= L->Length && !compare(*p++,e))
         ++i;
   if(i<=L->Length)
         return i;
   else
         return 0;
}

ElemType PriorElem(pList *L,ElemType cur_e,ElemType *pre_e)
{// 初始条件：顺序线性表L已存在
   // 操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，
   //         否则操作失败，pre_e无定义
      int i=2;
      ElemType *p=L->Elem+1;
      while(i < L->Length&& *p != cur_e)
      {
                p++;
                i++;
      }
      if(i > L->Length)
      {
                printf("当前线性表中并无此元素：%d！\n",cur_e);
                return FAILED;
                exit(0);
      }
      else
      {
                *pre_e = *--p;
                return *pre_e;
      }
}

ElemType NextElem(pList *L,ElemType cur_e,ElemType *next_e)
{// 初始条件：顺序线性表L已存在
   // 操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继，
   //         否则操作失败，next_e无定义
      int i=1;
      ElemType *p=L->Elem;
      while(i < L->Length&& *p != cur_e)
      {
                p++;
                i++;
      }
      if(i == L->Length)
      {
                printf("当前线性表中并无此元素：%d！\n",cur_e);
                return FAILED;
                exit(0);
      }
      else
      {
                *next_e = *++p;
                return *next_e;
      }
}

Status InsertList(pList *L,int i,ElemType e)
{// 初始条件：顺序线性表L已存在，1≤i≤ListLength(L)+1
   // 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1
      if(i < 1 || i > L->Length+1)
      {
                printf("您要插入的位置不在当前线性表范围！\n");
                return ERROR;
      }
      if(L->Length == L->ListSize) // 当前存储空间已满,增加分配
      {
                ElemType *newbase = (ElemType *)realloc(L->Elem,sizeof(ElemType)*(L->ListSize + LIST_INIT_SIZE));
                if(!newbase)
                {
                        printf("内存分配请求失败，你脸真的是太黑了！\n");
                        return ERROR;
                }
                L->Elem=newbase;
                L->ListSize += LIST_INIT_SIZE;
      }
      ElemType *q = &(L->Elem); //q存储插入位置
      ElemType *p;
      for(p = &(L->Elem);p >= q; p--)
                *(p+1) = *p;
      *q = e;
      L->Length++;
      return OK;
}

Status DeleteList(pList *L,int i,ElemType *e)
{// 初始条件：顺序线性表L已存在，1≤i≤ListLength(L)
   // 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1
      if(i < 1 || i > L->Length)
      {
                printf("需要删除的位置不存在！\n");
                return ERROR;
      }
      ElemType *p = &(L->Elem);
      *e = *p;
      ElemType *q=L->Elem + L->Length-1;
      for(p = p + 1;p <= q;p++)
                *(p-1) = *p;
      L->Length--;
      return OK;
}

void TraverseList(pList *L)
{      // 初始条件：顺序线性表L已存在
    // 操作结果：输出线性表所有元素
      int i;
      if(L->Length == 0)
      {
                printf("当前线性表为空！\n");
      }
      else
      {
                printf(      "当前线性表为：");
                for(i = 1; i <= L->Length ; i++)
                        printf("%d ", L->Elem);
                printf("\n");
      }
}

void SortList(pList *L)
{      //选择排序法
      if(L->Length == 0)
      {
                printf("当前线性表为空或不存在，无法排序！\n");
                exit(0);
      }
      Order order;
      printf("请输入排序方式，0表示从小到大排序，1表示从大到小排序：");
      scanf("%d",&order);
      int i,j,tmp,max,min;
      switch (order)
                {
                case 0:         //从小到大排序
                        for(i = 0;i < L->Length-1;i++)
                        {
                           min = i;
                           for(j = i;j < L->Length;j++)
                           {
                                 if(L->Elem > L->Elem)
                                           min = j;
                           }
                           tmp = L->Elem;
                           L->Elem = L->Elem;
                           L->Elem = tmp;
                        }
                        break;
                case 1:         //从大到小排序
                        for(i = 0;i < L->Length-1;i++)
                        {
                           max = i;
                           for(j = i;j < L->Length;j++)
                           {
                                    if(L->Elem < L->Elem)
                                           max = j;
                              }
                           tmp = L->Elem;
                           L->Elem = L->Elem;
                           L->Elem = tmp;
                        }
                        break;
                default:
                        break;
                }
      
}

void InvertList(pList *L)
{          //前后倒置
      int i,j,k=L->Length,tmp;
      for(i=0,j=k-1;i<k/2;i++,j--)
      {
                tmp=L->Elem;
                L->Elem=L->Elem;
                L->Elem=tmp;
      }
}

void Init()
{      //初始化函数
      printf("输入数字以完成操作\n");
      printf("初始化线性表：1\n");
      printf("销毁线性表：2\n");
      printf("置空线性表：3\n");
      printf("判断是否为空：4\n");
      printf("返回线性表长度：5\n");
      printf("获取第i个值：6\n");
      printf("数据元素判定：7\n");
      printf("获取某元素的前驱：8\n");
      printf("获取某元素的后继：9\n");
      printf("在第i个位置插入元素：10\n");
      printf("删除第i个位置的元素：11\n");
      printf("遍历输出当前线性表：12\n");
      printf("排序当前线性表：13\n");
      printf("倒置当前线性表：14\n");
      printf("退出：0\n");
}

int main(void)
{
      pList L;
      ElemType e; //e表示元素，用来存储对线性表操作的元素
      int i;      //i表示对线性表操作的位置
      srand((unsigned int)time(NULL));//用于产生随机数，此句话加上可使每次产生的随机数都不一样

      Init();
      int j=1;      //j指示进行哪一种操作

      while(j!=0)
          {
                  scanf("%d",&j);
                  switch (j)
                  {
                  case 0:
                        exit(0);
                        break;
                  case 1:
                        if(InitList(&L))
                        {
                                  printf("开始赋值\n");
                                  for(i=1;i<=8;++i)
                                  {
                                          e=rand()%100+1;
                                          InsertList(&L,i,e);
                                  }
                                  TraverseList(&L);
                        }
                              break;
                  case 2:
                        DestroyList(&L);
                        TraverseList(&L);
                        break;
                  case 3:
                        ClearList(&L);
                        TraverseList(&L);
                        break;
                  case 4:
                        if(ListEmpty(&L) == 0)
                                  printf("当前线性表为空！\n");
                        else
                        {
                                  printf("当前线性表不为空！\n");
                                  TraverseList(&L);
                        }
                                  break;
                  case 5:
                        i=ListLength(&L);
                        printf("当前线性表长度为%d\n",i);
                        break;
                  case 6:
                        printf("请输入获取第几个元素的值：");
                        scanf("%d",&i);
                        e=GetElem(&L,i,&e);
                        printf("第%d个元素是：%d\n",i,e);
                        break;
                  case 7:
                        printf("我还不知道这个函数啥意思呢，compare我也不知道是什么，你如果知道告诉下我！\n");
                        break;
                  case 8:
                        printf("请输入要获取哪个元素的前驱：");
                        scanf("%d",&i);
                        e=PriorElem(&L,i,&e);
                        printf("第%d个元素的前驱是：%d\n",i,e);
                        break;
                  case 9:
                        printf("请输入要获取哪个元素的后继：");
                        scanf("%d",&i);
                        e=NextElem(&L,i,&e);
                        printf("第%d个元素的后继是：%d\n",i,e);
                        break;
                  case 10:
                        printf("请输入要插入的位置及值：");
                        scanf("%d %d",&i,&e);
                        InsertList(&L,i,e);
                        TraverseList(&L);
                        break;
                  case 11:
                        printf("请输入要删除第几个元素：");
                        scanf("%d",&i);
                        DeleteList(&L,i,&e);
                        printf("删除的元素都是:%d\n",e);
                        break;
                  case 12:
                        TraverseList(&L);
                        break;
                  case 13:
                        SortList(&L);
                        TraverseList(&L);
                        break;
                  case 14:
                        InvertList(&L);
                        TraverseList(&L);
                        break;
                  default:
                        break;
                  }
          }
      return 0;
}













附赠 随书光盘内容 里面有程序演示
链接：https://pan.baidu.com/s/1smmkX-TiC2kzQ1cRV_OIOA 密码：o9zu

澧有兰 发表于 2018-6-8 23:04

共同学习，加油，谢谢分享

ks521 发表于 2018-6-8 23:17

一起学习，加油

一叶飘零G 发表于 2018-6-9 00:36

共同学习，感谢分享，加油！

huangyiyi 发表于 2018-6-9 00:56

共同学习，感谢分享，加油

查看完整版本: [笔记]一线性表