数据结构C-单链表（四）

在顺序表中，由于在内存中是相邻的，所以存取数据非常方便，但是在插入删除元素时需要移动大量的元素，这就造成了时间上的浪费。因此链式存储结构就可以克服顺序存储结构的缺点，但是顺序表的优点却成了链表的缺点。正所谓，鱼和熊掌二者不可兼得也。
链表由一个个节点组成，而节点由两部分组成，指针域和数据域。

节点的组成

数据域存放数据，指针域存放下一个节点的地址，若最后一个节点为空，则链表结束。
为了方便节点的操作，我们通常要在链表的最前面添加一个头节点（虚拟头节点），头节点的数据域随便存放什么数值，比如链表的长度，指针域指向NULL。

头节点
单链表的存储结构如下：

typedef struct Node {
  int data;
  struct Node * next;
} Node, LinkList;

1. 初始化链表

初始化只需为头节点分配内存空间，并且将头节点的指针域设为空即可。

void init(LinkList * list) {
  list = (Node *)malloc(sizeof(Node));
  if(list == NULL) {
    printf("内存分配失败！\n");
    exit(-1);
  }
  list->next = NULL;
}

2. 判断链表是否为空

判断链表是否为空只需将判断头节点的next是否为空即可。

bool isEmpty(LinkList * list) {
  return list->next == NULL
}

3. 查找元素

为了符合程序猿的思维，我们依旧从第0个开始算起。比如我们有以下链表 IMG_EA7DCAB00C1A-1.jpeg

我们要查询位置是2的元素。我们只要每遍历一个节点就让计数器加1，直到相等时，返回元素。

int get(LinkList * list, int index) {
  if(isEmpty(list)){
    printf("链表为空！");
    exit(-1);
  }
  int cnt=-1;
  while(list->next != NULL) {
    list = list->next;
    cnt++;
    if(cnt == index) {
      return list->data;
    }
  }
  return -1;
}

4. 定位元素

定位元素我们只需要每遍历一个节点，然后计数器+1，直到节点的值和我们想要的值相等时返回计数器。

int locatedEl(LinkList * list, int el) {
  int cnt=-1;
  while(list->next != NULL) {
    list = list->next;
    cnt++;
    if(list->data == el) {
      return cnt;
    }
  }
  return -1;
}

5. 获得链表长度

获得链表长度，我们只要每遍历一个节点就让计数器加1，直到为NULL为止

int getLength(LinkList * list) {
  int cnt=0;
  while(list->next != NULL) {
    list = list->next;
    cnt++;
  }
  return cnt;
}

6. 打印链表

打印链表，我们依旧每遍历一个节点，就打印一次数据。

void echoList(LinkList * list) {
  while(list->next != NULL) {
    list = list->next;
    printf("%d->",list->data);
  }
  printf("NULL");
}

7. 插入元素

插入元素，就是将元素el插入到链表的第index位置。首先需要找到第index个元素的前一个节点，接着把新节点的next指向前一个节点的next，然后把前一个节点的next指向新的节点。假设我们要插入元素5，那么我们首先要创建一个节点newNode，接着把pre的next节点的值赋给newNode的next节点，然后把newNode的值赋给pre的next。 IMG_F92F21015C6C-2.jpeg

void add(LinkList * list, int index, int e) {
    Node *newNode = (Node *) malloc(sizeof(Node));
    if(newNode == NULL) {
        printf("Add failed! 内存空间分配失败。");
        exit(-1);
    }
    int cnt=-1;
    newNode->data = e;
    if(isEmpty(list)) {
        newNode->next = list->next;
        list->next = newNode;
    }
    while(list->next != NULL) {
        list = list->next;
        cnt++;
        if(cnt == index-1) {
            newNode->next = list->next;
            list->next = newNode;
        }
    }}

8. 删除元素

删除元素就是将链表中的第index个节点删除，并返回该节点的值。例如我们要删除index=2的元素，如下图： IMG_CD5CC7FA736D-1.jpeg

首先我们要找到第index个元素的前一个节点，然后把pre的next的值赋给pre的next的next值即可。

int deleteEl(LinkList * list, int index) {
    int cnt=-1;
    int delEl=0;
    while(list->next != NULL) {
        list = list->next;
        cnt++;
        if(cnt == index-1) {
            delEl = list->next->data;
            list->next = list->next->next;
        }
    }
    return delEl;
}

代码1:

//
//  main.c
//  LinkList
//
//

#include <stdio.h>
#include <stdlib.h>

#define true 1
#define false 0
typedef int bool;

typedef struct Node {
    int data;
    struct Node * next;
} Node, LinkList;

void init(LinkList * list);
bool isEmpty(LinkList * list);
int get(LinkList * list, int index);
int locatedEl(LinkList * list, int el);
int getLength(LinkList * list);
void echoList(LinkList * list);
void add(LinkList * list, int index, int e);
int deleteEl(LinkList * list, int index);

void init(LinkList * list) {
    list = (Node *)malloc(sizeof(Node));
    if(list == NULL) {
        printf("内存分配失败！\n");
        exit(-1);
    }
    list->next = NULL;
}

bool isEmpty(LinkList * list) {
    return list->next == NULL;
}

int get(LinkList * list, int index) {
    if(isEmpty(list)){
        printf("链表为空！");
        exit(-1);
    }
    int cnt=-1;
    while(list->next != NULL) {
        list = list->next;
        cnt++;
        if(cnt == index) {
            return list->data;
        }
    }
    return -1;
}

int locatedEl(LinkList * list, int el) {
    int cnt=-1;
    while(list->next != NULL) {
        list = list->next;
        cnt++;
        if(list->data == el) {
            return cnt;
        }
    }
    return -1;
}

int getLength(LinkList * list) {
    int cnt=0;
    while(list->next != NULL) {
        list = list->next;
        cnt++;
    }
    return cnt;
}

void echoList(LinkList * list) {
    while(list->next != NULL) {
        list = list->next;
        printf("%d->",list->data);
    }
    printf("NULL\n");
}

void add(LinkList * list, int index, int e) {
    Node *newNode = (Node *) malloc(sizeof(Node));
    if(newNode == NULL) {
        printf("Add failed! 内存空间分配失败。");
        exit(-1);
    }
    int cnt=-1;
    newNode->data = e;
    if(isEmpty(list)) {
        newNode->next = list->next;
        list->next = newNode;
    }
    while(list->next != NULL) {
        list = list->next;
        cnt++;
        if(cnt == index-1) {
            newNode->next = list->next;
            list->next = newNode;
        }
    }
}

int deleteEl(LinkList * list, int index) {
    int cnt=-1;
    int delEl=0;
    while(list->next != NULL) {
        list = list->next;
        cnt++;
        if(cnt == index-1) {
            delEl = list->next->data;
            list->next = list->next->next;
        }
    }
    return delEl;
}

int main(int argc, const char * argv[]) {
    // insert code here...
    printf("Hello, World!\n");
    
    LinkList list;
    init(&list);
    
    for (int i=0; i<5; i++) {
        add(&list, i, i);
    }
    
    echoList(&list);
    
    deleteEl(&list, 3);
    
    echoList(&list);
    
    printf("2 = %d\n",get(&list, 2));
    printf("len = %d\n",getLength(&list));
    
    return 0;
}

代码2:

//
//  main.c
//  LinkedList
//  单链表的实现
//
//

#include <stdio.h>
#include <stdlib.h>

//定bool类型的值true|false
#define true 1
#define false 0

#define EXIT -1
#define ZERO 0

//自定义bool数据类型
typedef int bool;

typedef struct Node{
    int data;
    struct Node *next;
} Node;

typedef struct LinkedList{
    Node *node;
    int size;
}LinkedList;

//----------------------------------------------函数声明----------------------------------------------------------------

//初始化
void init(LinkedList *list);

//获得链表的长度
int getSize(LinkedList *list);

//链表是否为空
bool isEmpty(LinkedList *list);

//在index位置添加元素e
void add(LinkedList *list, int index, int e);

//在头部添加元素e
void addHead(LinkedList *list, int e);

//在尾部添加元素e
void addTail(LinkedList *list, int e);

//链表中是否包含元素e
bool contains(LinkedList *list, int e);

//查找第index位置上的元素，index从0开始
int get(LinkedList *list, int index);

//查找第一个元素
int getHead(LinkedList *list);

//查找最后一个元素
int getTail(LinkedList *list);

//修改元素
void set(LinkedList *list, int index, int e);

//删除index位置上的元素，index从0开始
int delete(LinkedList *list, int index);

//删除第一个元素
int deleteHead(LinkedList *list);

//删除最后一个元素
int deleteTail(LinkedList *list);

//查找第一个元素e的位置，没有查到则返回-1
int indexOf(LinkedList *list, int e);

//销毁数组
void destory(LinkedList *list);

//显示链表信息
void show(LinkedList *list);

//自定义错误提示
void error(char* msg);

//自定义警告提示
void warning(char* msg);

//----------------------------------------------函数实现----------------------------------------------------------------

void init(LinkedList *list) {
    //创建虚拟头节点，为虚拟头节点分配内存
    Node *dummyHead = (Node *)malloc(sizeof(Node));
    if (dummyHead == NULL) {
        error("Node memory allocation failed.");
        exit(EXIT);
    }
    //虚拟头节点的next设为空
    dummyHead->next = NULL;
    //把虚拟头节点赋值给list的node
    list->node = dummyHead;
}

int getSize(LinkedList *list) {
    return list->size;
}

bool isEmpty(LinkedList *list) {
    return list->size == ZERO;
}

void add(LinkedList *list, int index, int e) {
    if (index<0 && index>=list->size) {
        error("Index out of range.");
        exit(EXIT);
    }
    Node *node = (Node *)malloc(sizeof(Node));
    if (node == NULL) {
        error("Node memory allocation failed.");
        exit(EXIT);
    }
    node->data=e;
    
    Node *prev = list->node;
    for (int i=0; i<index; i++) {
        prev = prev->next;
    }
    node->next = prev->next;
    prev->next = node;
    
    list->size++;
}

void addHead(LinkedList *list, int e) {
    add(list, 0, e);
}

void addTail(LinkedList *list, int e) {
    add(list, list->size, e);
}

bool contains(LinkedList *list, int e) {
    Node *node = list->node->next;
    while (node != NULL) {
        if (node->data == e) {
            return true;
        }
        node = node->next;
    }
    return false;
}

int get(LinkedList *list, int index) {
    if (index<0 && index>=list->size) {
        error("Index out of range.");
        exit(EXIT);
    }
    Node *node = list->node->next;
    for (int i=0; i<index; i++) {
        node = node->next;
    };
    return node->data;
}

int getHead(LinkedList *list) {
    return get(list, 0);
}

int getTail(LinkedList *list) {
    return get(list, list->size-1);
}

void set(LinkedList *list, int index, int e) {
    if (index<0 && index>=list->size) {
        error("Index out of range.");
        exit(EXIT);
    }
    Node *node = list->node->next;
    for (int i=0; i<index; i++) {
        node = node->next;
    };
    node->data = e;
}

int delete(LinkedList *list, int index) {
    if (index<0 && index>=list->size) {
        error("Index out of range.");
        exit(EXIT);
    }
    if (isEmpty(list)) {
        error("LinkedList is empty.");
        exit(EXIT);
    }
    Node *prev = list->node;
    for (int i=0; i<index; i++) {
        prev = prev->next;
    }
    Node *cur = prev->next;
    prev->next = cur->next;
    list->size--;
    return cur->data;
}

int deleteHead(LinkedList *list) {
    return delete(list, 0);
}

int deleteTail(LinkedList *list) {
    return delete(list, list->size-1);
}

int indexOf(LinkedList *list, int e) {
    Node *node = list->node->next;
    for (int i=0; i<list->size; i++) {
        if (node->data == e) {
            return I;
        }
        node = node->next;
    };
    return -1;
}

void destory(LinkedList *list) {
    free(list);
    list = NULL;
}

void show(LinkedList *list) {
    printf("LinkedList: size=%d, ",list->size);
    Node *node = list->node->next;
    while (node != NULL) {
        printf("%d->",node->data);
        node = node->next;
    }
    printf("null\n");
}

void error(char* msg) {
    printf("\n---------------------------------------------------------------------------\n");
    printf("ERROR: %s", msg);
    printf("\n---------------------------------------------------------------------------\n\n");
}

void warning(char* msg) {
    printf("\n---------------------------------------------------------------------------\n");
    printf("WARNING: %s", msg);
    printf("\n---------------------------------------------------------------------------\n\n");
}

//----------------------------------------------main函数----------------------------------------------------------------

int main(int argc, const char * argv[]) {
    
    LinkedList list;
    
    init(&list);
    
    show(&list);
    
  
    
    for (int i=0; i<5; i++) {
        add(&list, i, i);
        show(&list);
    }
    
    delete(&list, 0);
    show(&list);
    
    if (contains(&list, 0)) {
        printf("true\n");
    }else{
        printf("false\n");
    }
    
    printf("get 1: %d\n", get(&list, 1));
    
    printf("getFirst: %d\n", getHead(&list));
    
    printf("getLast: %d\n", getTail(&list));
    
    printf("indexOf 3: %d\n", indexOf(&list, 3));
    
    set(&list, 2, 1000);
    show(&list);
    
    addHead(&list, -1);
    show(&list);
    
    delete(&list, 0);
    show(&list);
    
    deleteHead(&list);
    show(&list);
    
    deleteTail(&list);
    show(&list);
    
    addTail(&list, 10);
    show(&list);
    
//        destory(&list);
    
    addTail(&list, 10);
    show(&list);
    
    return 0;
}