数据结构之线性表的基本操作

线性表的顺序存储结构 — 顺序表

首先定义顺序表的结构
#define LIST_SIZE 100
typedef int Datatype ;
typedef struct{
Datatype* data;
int length;//线性表的真实长度
int listsize;//线性表创造的数组的长度
}seqlist;

/*InitList(&L)
初始条件：无
操作结果：构造一个空的线性表。成功返回0出错返回-1*/

int InitList(seqlist *L)
{
    L->data = (Datatype *)malloc(sizeof(Datatype)*LIST_SIZE);
    if (L->data == NULL)
        return -1;
    L->length = 0;
    L->listsize = LIST_SIZE;
    printf("initial finish\n");
    return 0;
}

/*DestroyList(&L)
初始条件：线性表L已经存在
操作结果:销毁线性表L。成功返回0出错返回-1*/

int DestroyList(seqlist *L)
{
    while (!L->data)
    free(L->data);
    L->length = 0;
    printf("destroy finish\n");
    return 0;

}

/*ListEmpty(L)
初始条件：线性表L已经存在
操作结果：若L为空表，返回0，否则返回-1*/

int ListEmpty(seqlist L)
{
    if (L.length == 0)
    {
        printf("list is empty\n");
        return 0;
    }
    else
        return -1;
}

/*ListLength (L)
初始条件：线性表L已经存在
操作结果：返回表的长度，失败返回-1*/


int ListLength(seqlist L)
{

    return L.length;
}

/*Getelem(L,i,&e)
初始条件：线性表L已经存在1=<i<=LIST_SIZE
操作结果：用e返回L中第i个元素的值成功返回0出错返回-1*/
int Getelem(seqlist L, int i, Datatype *e)
{
    if (i < 0 || i >LIST_SIZE)
    {
        printf("position error\n");
        return -1;
    }
    *e = L.data[i];
    return 0;

}
/*Locateelem(L,e)
初始条件：线性表L已经存在
操作结果：返回L中第一个和e相等的***，若元素不存在，则返回-1*/
int Locateelem(seqlist L, Datatype e)
{

    int i;//遍历整个链表，直到结尾若没找到返回-1
    for (i = 0; i < L.length; i++)
    {
        if (L.data[i] == e)
            return i+1;
    }
    return -1;
}
/*Priorelem(L,cur_e,&pre_e)
初始条件：线性表已经存在
操作结果：若cur_e是L中的元素，且不是第一个，则用pre_e返回它的前驱元素，否则返回错误-1，成功返回0*/
int Priorelem(seqlist L, Datatype cur_e, Datatype *pre_e)
{
    int i = 0;
    if (cur_e == L.data[0])
        return -1;
    i = Locateelem(L, cur_e);
    if (i== -1)
        return -1;
    else
    {
        *pre_e = L.data[i - 2];
        return 0;
    }

}
/*Nextelem(L,cur_e,&next_e)
初始条件：线性表已经存在
操作结果：若cur_e是L中的元素，且不是最后一个，则用next_e返回它的前驱元素，否则返回错误-1，成功返回0*/
int Nextelem(seqlist L, Datatype cur_e, Datatype *next_e)
{
    int i = 0;
    if (cur_e == L.data[ListLength(L)-1])
        return -1;
    i = Locateelem(L, cur_e);
    if (i == -1)
        return -1;
    else
    {
        *next_e = L.data[i];
        return 0;
    }

}
/*ListInsert(&L,i,e)
初始条件：线性表L已经存在
操作结果：在L中第i个位置之前插入新的数据，表长加1，返回0成功，-1错误*/
int ListInsert(seqlist *L, int i, Datatype e)
{
    if (i<1 || i>L->listsize)
    {
        printf("position error\n");
        return -1;
    }
    if (L->length >= L->listsize)
        L->data = (Datatype *)realloc(L->data, (LIST_INCREMENT + LIST_SIZE)*sizeof(Datatype));
    if (!L->data)
    {
        printf("realloc error\n");
        return -1;
    }
    Datatype *q=NULL;
    q = &L->data[i - 1];//插入位置
    Datatype *p = NULL;
    for (p = &L->data[L->length - 1]; p >= q;p--)//从最后一个位置开始依次把前面的值赋值给后一个位置
    {
        *(p + 1) = *p;
    }
    *q = e;
    L->length++;
    L->listsize += LIST_INCREMENT;
    return 0;


}
/*Listdelete(&L,i,&e)
初始条件：线性表L存在
操作结果：删除L中序号为i的元素，并将其值由e带回,成功返回0，出错返回-1*/

int Listdelete(seqlist *L, int i, Datatype *e)
{

    if (i<1 || i>L->listsize)
    {
        printf("postion error:\n");
        return -1;
    }
    Datatype *q = NULL;
    Datatype *p = NULL;
    q = &L->data[i - 1];//删除元素位置
    *e = *q;
    p = &L->data[L->length - 1];//表尾位置
    while (q <= p)
    {
        *q = *(q + 1);
        q++;
    }
    L->length--;
    return 0;
    }

链表

#include <stdio.h>
#include <stdlib.h> //用于malloc，同样也可以使用malloc.h
#define Elementtype int //定义你需要使用的链表类型，这里以整形为例
typedef struct NODE {
  Elementtype data;  //需要的数据
  struct NODE *next; //指向下个节点的指针
} node;              //为了方便而是用typedef，注意，上方定义下个节点的指针需要写完整的结构体
//因为在这句话出现之前我们还没有定义node
node *creat(int n); //创建链表的函数，n为链表初始需要的长度,返回头节点指针
node *insert(node *head, int pos, Elementtype data); //将data插入到第pos个位置
node *del(node *head, int pos); //删除位置pos下的数据
void print(node *head);         //输出链表中的数据内容
int main() {
  int in;
  node *p = NULL;
  printf("请输入编号选择你想进行的操作：\n1、创建链表\n2、在链表中插入元素\n3、"
         "删除链表内容\n4、输出当前链表中的内容\nq、退出\n请选择：");
  while (scanf("%d", &in) == 1) {
    if (in == 1) {
      int len;
      printf("请输入你要创建的链表的长度:");
      scanf("%d", &len);
      p = creat(len);
    } else if (in == 4)
      print(p);
    else if (in == 2) {
      int pos, tmp;
      printf("请输入插入的位置：");
      scanf("%d", &pos);
      printf("请输入插入的内容：");
      scanf("%d", &tmp);
      p = insert(p, pos, tmp);
    } else if (in == 3) {
      int pos;
      printf("请输入你要删除的位置\n");
      scanf("%d", &pos);
      p = del(p, pos);
    } else
      printf("您的输入有误，请重新输入。\n");
    printf(
        "请输入编号选择你想进行的操作：\n1、创建链表\n2、在链表中插入元素\n3、"
        "删除链表内容\n4、输出当前链表中的内容\nq、退出\n请选择：");
  }
  return 0;
}
node *creat(int n) {
  if (!n) {
    printf("不支持创建空链表\n");
    return NULL;
  } else {
    printf("请输入要创建的链表的初始内容：\n");
    node *head = (node *)malloc(sizeof(node));
    scanf("%d", &head->data);
    head->next = NULL;
    node *last = head;
    while (--n) {
      node *p = (node *)malloc(sizeof(node));
      scanf("%d", &p->data);
      p->next = NULL;
      last->next = p;
      last = p;
    }
    return head;
  }
}
void print(node *head) {
  node *p = head;
  while (p->next != NULL) {
    printf("%d\n", p->data);
    p = p->next;
  }
  printf("%d\n", p->data);
}
node *insert(node *head, int pos, Elementtype data) {
  int cnt = 1;
  node *p = head;
  node *fm = p;
  node *tmp = (node *)malloc(sizeof(node));
  tmp->data = data;
  tmp->next = NULL;
  if (pos == 1) {
    tmp->next = head;
    return tmp;
  }
  while (cnt != pos) {
    cnt++;
    fm = p;
    p = p->next;
    if (p->next == NULL) {
      if (cnt + 1 == pos)
        p->next = tmp;
      else
        printf("链表没这么长\n");
      return head;
    }
  }
  fm->next = tmp;
  tmp->next = p;
  return head;
}
node *del(node *head, int pos) {
  node *p = head;
  if (pos == 1) {
    p = p->next;
    free(head);
    return p;
  }
  node *fm = p;
  int cnt = 1;
  while (cnt != pos) {
    cnt++;
    fm = p;
    p = p->next;
    if (p->next == NULL && cnt != pos) {
      printf("当前链表没这么长\n");
      return head;
    }
  }
  if (p->next == NULL) {
    fm->next = NULL;
    free(p);
  } else {
    fm->next = p->next;
    free(p);
  }
  return head;
}