vlambda博客
学习文章列表

//// DoubleLinkList.h// chapter-04双向链表//// Created by Mac on 2020/5/19.// Copyright © 2020 Mac. All rights reserved.//
#ifndef DoubleLinkList_h#define DoubleLinkList_h
#include <stdio.h>#include <stdbool.h>#include <stdlib.h>

#define OK 1#define ERROR 0#define NOT_FOUND_ELEMENT -1

typedef int Status; //函数返回状态 OK ERRORtypedef int ElemType; //元素类型
//节点的设计typedef struct Node{ struct Node *pre; struct Node *next; ElemType element;}Node;
//双向链表的创建typedef struct DoubleLinkList{ Node* first; Node* last; int length;}DoubleLinkList;

/*1.线性表初始化*/DoubleLinkList* initLinkList(void);
/*2.插入数据*/Status insertList(int index,ElemType element,DoubleLinkList *linkList);
/*3.删除数据*/Status deleteList(int index,DoubleLinkList *linkList);
/*4.尾插入*/Status insertListTail(ElemType element,DoubleLinkList *linkList);/**/
/*5.遍历*/void display(DoubleLinkList* linkList);
/*6.判空操作*/bool listEmpty(const DoubleLinkList* linkList);
/*7.清空操作*/Status clearList(DoubleLinkList* linkList);
/*8.获取元素的位置*/int indexOf(ElemType e,DoubleLinkList* linkList);
/*9.通过位置获取元素的值*/ElemType getElem(int index,DoubleLinkList* linkList);
/*10.判断是否包含某个元素*/bool contains(ElemType e,DoubleLinkList* linkList);
/*11.获取线性表的长度*/int listLength(const DoubleLinkList* linkList);
/*12 设置index对应的元素,并返回原来的元素值*/ElemType set(ElemType e,int index,DoubleLinkList* linkList);
#endif /* DoubleLinkList_h */

//// DoubleLinkList.c// chapter-04双向链表//// Created by Mac on 2020/5/19.// Copyright © 2020 Mac. All rights reserved.//
#include "DoubleLinkList.h"

void checkRange(int index,DoubleLinkList *linkList){  if (index < 0 || index >= linkList->length) { printf("异常了啦！！！index: %d 线性表长度 %d",index,linkList->length); exit(0); }}

void checkOfAddRange(int index,DoubleLinkList *linkList){  if (index < 0 || index > linkList->length) { printf("异常了啦！！！index: %d 线性表长度 %d",index,linkList->length); exit(0); }}

/*返回下标为index的节点*/Node *findNode(int index,DoubleLinkList *linkList){ checkRange(index, linkList); Node *current = NULL; if (index<linkList->length>>1) { current = linkList->first; for (int i= 0; i < index; i++) { current = current->next; } }else{ current = linkList->last; for (int i= linkList->length-1; i > index; i--) { current = current->pre; } } return current;}
/*1.线性表初始化*/DoubleLinkList* initLinkList(void){ DoubleLinkList* list =(DoubleLinkList*)malloc(sizeof(DoubleLinkList)); if (!list) { printf("初始化失败"); exit(0); } list -> length = 0; list -> first = NULL; list -> last = NULL; return list;}
/*2.插入数据*/Status insertList(int index,ElemType element,DoubleLinkList *linkList){ checkOfAddRange(index, linkList) if (linkList->length == index) {//在尾部插入 Node *lastNode = linkList->last; Node *newNode = (Node* )malloc(sizeof(Node)); newNode->element = element; newNode->next = NULL; linkList->last = newNode; if (!newNode) { printf("申请内存失败"); return ERROR; } if (lastNode==NULL) {//当没有元素的时候 linkList->first = linkList->last; newNode->pre = NULL;  }else{ lastNode->next = newNode; newNode->pre = lastNode; } }else{ Node *nextNode = findNode(index, linkList); Node *preNode = nextNode->pre; Node *newNode = (Node* )malloc(sizeof(Node)); if (!newNode) { return ERROR; } newNode->pre = preNode; newNode->next = newNode; newNode->element = element; nextNode->pre = newNode; if (preNode==NULL) { //插入在下标为0的时候 linkList->first =newNode; }else{ preNode->next =newNode; } } linkList->length++;  return OK; }
/*3.删除数据*/Status deleteList(int index,DoubleLinkList *linkList){ checkRange(index, linkList);  if (index==linkList->length-1) { //删除的是最后一个节点 if (index==0) {//当只有一个节点的时候 free(linkList->last); linkList->last = NULL; linkList-> first = NULL; }else{ Node *lastNode = linkList->last; linkList->last = linkList->last->pre; free(lastNode); }  }else{ Node* node = findNode(index, linkList);//这个是要删除的 Node* preNode = node->pre; Node* nextNode = node->next; if (preNode==NULL) {//删除的是第一个节点 linkList->first = nextNode; nextNode->pre = NULL; }else{ nextNode->pre = preNode; preNode->next = nextNode; } free(node);  } linkList->length--;  return OK;}

/*4.尾插入*/Status insertListTail(ElemType element,DoubleLinkList *linkList){  return insertList(linkList->length, element, linkList);}
/*5.遍历*/void display(DoubleLinkList* linkList){  Node *node = linkList->first; printf("size = %d [ ",linkList->length); for (int i=0; i<linkList->length; i++) { printf("%d ",node->element); node= node->next; } printf("]\n");}
/*6.判空操作*/bool listEmpty(const DoubleLinkList* linkList){ return linkList->length == 0; }
/*7.清空操作*/Status clearList(DoubleLinkList* linkList){  Node* currentNode = linkList->first; Node* p = NULL; for (int i = 0; i<linkList->length; i++) { p = currentNode->next; free(currentNode); currentNode = p; } linkList->first = NULL; linkList->last = NULL; linkList->length = 0; return OK;}
/*8.获取元素的位置*/int indexOf(ElemType e,DoubleLinkList* linkList){ Node* current = linkList->first; for (int i = 0 ; i<linkList->length; i++) { if (current->element == e) { return i; } current = current->next; } return NOT_FOUND_ELEMENT;}/*9.通过位置获取元素的值*/ElemType getElem(int index,DoubleLinkList* linkList){  Node *node = findNode(index, linkList); return node->element; }
/*10.判断是否包含某个元素*/bool contains(ElemType e,DoubleLinkList* linkList){ return indexOf(e, linkList)!=NOT_FOUND_ELEMENT;}
/*11.获取线性表的长度*/int listLength(const DoubleLinkList* linkList){ return linkList->length;}
/*12 设置index对应的元素,并返回原来的元素值*/ElemType set(ElemType e,int index,DoubleLinkList* linkList){ Node* node = findNode(index, linkList); ElemType oldData = node->element; node->element = e; return oldData;}

//// main.c// chapter-04双向链表//// Created by Mac on 2020/5/17.// Copyright © 2020 Mac. All rights reserved.//
#include <stdio.h>#include "DoubleLinkList.h"
int main(int argc, const char * argv[]) { // insert code here... DoubleLinkList* list = initLinkList(); printf("插入验证:\n"); insertList(0, 1, list); insertList(1, 2, list); insertList(2, 3, list); insertListTail(4, list); display(list);  printf("删除验证:\n"); deleteList(0,list); deleteList(1,list); deleteList(0,list); deleteList(0, list);
 display(list);
 printf("尾插入法验证:\n\n"); insertListTail(1, list); insertListTail(2, list); insertListTail(3, list); display(list);  printf("获取元素位置验证:\n"); printf("元素位置是:%d\n\n",indexOf(2, list));  printf("验证获取元素:\n"); printf("元素是:%d\n\n",getElem(1, list));  printf("验证表长:\n"); printf("元素是:%d\n\n",listLength (list));  printf("验证是否包含:\n"); printf("元素是否包含:%d\n\n",contains(5, list));  printf("验证修改元素的值:\n"); printf("修改前:\n"); display(list); set(5, 0, list); printf("修改后:\n"); display(list); printf("元素是否含:%d\n\n",contains(5, list));  printf("\n"); printf("清空操作验证:\n"); clearList(list);  printf("是否清空%d \n\n",listEmpty(list)); insertList(0, 1, list); insertList(1, 2, list); insertList(2, 3, list); display(list); }

/*2.插入数据*/Status insertList(int index,ElemType element,DoubleLinkList *linkList){  checkOfAddRange(index, linkList); Node* firstNode = linkList->first; Node* lastNode = linkList->last;  if (linkList->length == index) {//当插入在末尾的位置 Node* newNode = (Node*)malloc(sizeof(Node)); linkList->last = newNode;  if (!newNode) { printf("创建失败!!!\n"); return ERROR; }  newNode->element = element; if (linkList->first == NULL) {//当没有元素的时候  linkList->first = linkList->last; newNode->next = newNode; newNode->pre = newNode;  }else{//在最后一个位置添加 newNode->next = firstNode; newNode->pre = lastNode; lastNode->next =newNode; firstNode->pre = newNode; }  }else{ Node *nextNode = findNode(index, linkList); Node *newNode = (Node*)malloc(sizeof(Node)); Node *preNode = nextNode->pre; if (!newNode) { return ERROR; } newNode->pre= preNode; newNode->next = nextNode; nextNode->pre = newNode; preNode->next = newNode; newNode->element =element;
 if (preNode==lastNode) { //插入在0的位置 linkList->first = newNode; }  } linkList->length++;   return OK;}
/*3.删除数据*/Status deleteList(int index,DoubleLinkList *linkList){ checkRange(index, linkList); Node* node = findNode(index, linkList); Node* preNode = node->pre; Node* nextNode = node->next;  if (linkList->first==linkList->last) { //当只有一个节点的时候 linkList->first = NULL; linkList->last = NULL; }else{ preNode->next = node->next; nextNode->pre = node->pre; if(node==linkList->first){//当删除的头部节点 linkList->first = nextNode; } if(node == linkList->last){//当删除的尾元节点 linkList->last = preNode; } } free(node); linkList->length--;  return OK;}