单链表作业（03次）

作者: crabor | 来源:发表于2018-04-16 20:10 被阅读0次

单链表 C++
线性表：顺序表和链表
单向链表算法
链表基本操作
25_静态单链表的实现
线性表的链式存储-单链表
Algorithm小白入门 -- 单链表
单链表反转
JavaScript数据结构2——单链表
链表

#include <cstdlib>
#include <ctime>
#include <iostream>

using namespace std;

#define ElemType int
#define MAX 15

#define HEAD_NODE
 
typedef enum { OK = 1, ERROR = 0 } Status;
typedef enum { YES = 1, NO = 0 } Bool;

typedef struct Node {
  struct Node *next;
  ElemType value;
} Node;

#ifdef NO_HEAD_NODE
// Status InitList(Node **ppList);
Status DestroyList(Node **ppList);
Bool IsListEmpty(Node **ppList);
unsigned ListLength(Node **ppList);
Status DisplayList(Node **ppList);
Bool GetElem(Node **ppList, int i, ElemType *e);
int LocateElem(Node **ppList, ElemType e);
Status ListInsert(Node **ppList, ElemType value);
Status ListDelete(Node **ppList, ElemType e);

Status DestroyList(Node **ppList) {
  Node *cur = *ppList, *pre = NULL;
  while (cur != NULL) {
    pre = cur;
    cur = cur->next;
    free(pre);
    pre = NULL;
  }
  return OK;
}

/*
Status DestroyList(Node **pList){//递归销毁链表法
    if(*pList!=NULL){
        DestroyList((*pList)->next);
        free(*pList);
    }
    return OK;
}
*/

Bool IsListEmpty(Node **ppList) {
  if (*ppList == NULL) {
    return YES;
  } else {
    return NO;
  }
}

unsigned ListLength(Node **ppList) {
  Node *cur = *ppList;
  unsigned len = 0;
  while (cur != NULL) {
    len++;
    cur = cur->next;
  }
  return len;
}

Status DisplayList(Node **ppList) {
  Node *cur = *ppList;
  while (cur != NULL) {
    cout << cur->value << " ";
    cur = cur->next;
  }

  cout << endl;
  return OK;
}

Bool GetElem(Node **ppList, int i, ElemType *e) {
  Node *cur = *ppList;
  int j = 0;
  if (i <= 0) {
    return NO;
  }
  while (j < i && cur != NULL) {
    j++;
    cur = cur->next;
  }
  if (cur == NULL) {
    return NO;
  } else {
    *e = cur->value;
    return YES;
  }
}

int LocateElem(Node **ppList, ElemType e) {
  Node *cur = *ppList;
  int i = 0;
  while (cur != NULL) {
    i++;
    if (cur->value == e) {
      return i;
    }
    cur = cur->next;
  }
  return 0;
}

Status ListInsert(Node **ppList,
                  ElemType value) { 
  Node *cur, *newNode;

  newNode = (Node *)malloc(sizeof(Node));
  if (newNode == NULL) {
    return ERROR;
  }

  newNode->value = value;

  while (
      cur = *ppList,
      cur != NULL &&
          cur->value <
              value) { 
    ppList = &cur->next;
  }

  *ppList = newNode;
  newNode->next = cur;

  return OK;
}

Status ListDelete(Node **ppList, ElemType e) {
  Node *cur;
  while (cur = *ppList, cur != NULL && cur->value != e) {
    ppList = &cur->next;
  }
  if (cur == NULL) {
    return ERROR;
  } else {
    *ppList = cur->next;
    free(cur);
  }
  return OK;
}

int main(void) {
  Node *LinkedList = NULL;
  int n = MAX;
  ElemType radElem, e;

  srand((unsigned)time(NULL));
  while (n--) {
    radElem = rand() % 101;
    ListInsert(&LinkedList, radElem);
  }

  DisplayList(&LinkedList);

  if (IsListEmpty(&LinkedList)) {
    cout << "The LinkedList is empty" << endl;
  } else {
    unsigned len = ListLength(&LinkedList);
    cout << "The length of LinkedList is " << len << endl;
  }

  if (GetElem(&LinkedList, 20, &e) == YES) {
    cout << "The number in 20th position is " << e << endl;
  } else {
    cout << "The length of LinkedList is shortter than 20" << endl;
  }

  int i = LocateElem(&LinkedList, 20);
  if (i > 0) {
    cout << "The 20 is already exist in the LinkedList and it is in " << i
         << "th position." << endl;
  } else {
    cout << "The 20 isn`t exist in the LinkedList" << endl;
  }

  ListInsert(&LinkedList, 30);
  DisplayList(&LinkedList);

  ListDelete(&LinkedList, 30);
  DisplayList(&LinkedList);

  return 0;
}
#endif

#ifdef HEAD_NODE
Status InitList(Node *&pList);
Status DestroyList(Node *pList);
Bool IsListEmpty(Node *pList);
unsigned ListLength(Node *pList);
Status DisplayList(Node *pList);
Bool GetElem(Node *pList, int i, ElemType *e);
int LocateElem(Node *pList, ElemType e);
Status ListInsert(Node *pList, ElemType value);
Status ListDelete(Node *pList, ElemType e);

Status InitList(Node *&pList){
    pList=(Node *)malloc(sizeof(Node));
    if(pList==NULL){
      return ERROR;
    }
    pList->next = NULL;
    return OK;
}

Status DestroyList(Node *pList) {
  Node *cur = pList, *pre = NULL;
  while (cur != NULL) {
    pre = cur;
    cur = cur->next;
    free(pre);
    pre = NULL;
  }
  return OK;
}

/*
Status DestroyList(Node *pList){//递归销毁链表法
    if(pList!=NULL){
        DestroyList(pList->next);
        free(pList);
    }
    return OK;
}
*/

Bool IsListEmpty(Node *pList) {
  pList = pList->next;
  if (pList == NULL) {
    return YES;
  } else {
    return NO;
  }
}

unsigned ListLength(Node *pList) {
  pList = pList->next;
  Node *cur = pList;
  unsigned len = 0;
  while (cur != NULL) {
    len++;
    cur = cur->next;
  }
  return len;
}

Status DisplayList(Node *pList) {
  pList = pList->next;
  Node *cur = pList;
  while (cur != NULL) {
    cout << cur->value << " ";
    cur = cur->next;
  }

  cout << endl;
  return OK;
}

Bool GetElem(Node *pList, int i, ElemType *e) {
  pList = pList->next;
  Node *cur = pList;
  int j = 0;
  if (i <= 0) {
    return NO;
  }
  while (j < i && cur != NULL) {
    j++;
    cur = cur->next;
  }
  if (cur == NULL) {
    return NO;
  } else {
    *e = cur->value;
    return YES;
  }
}

int LocateElem(Node *pList, ElemType e) {
  pList = pList->next;
  Node *cur = pList;
  int i = 0;
  while (cur != NULL) {
    i++;
    if (cur->value == e) {
      return i;
    }
    cur = cur->next;
  }
  return 0;
}

Status ListInsert(Node *pList,ElemType value) {

  Node *cur,*pre=pList, *newNode;
  pList = pList->next;

  newNode = (Node *)malloc(sizeof(Node));
  if (newNode == NULL) {
    return ERROR;
  }

  newNode->value = value;

  for (cur = pList; cur != NULL && cur->value < value;pre=cur,cur=cur->next)
    ;
  pre->next = newNode;
  newNode->next = cur;

  return OK;
}

Status ListDelete(Node *pList, ElemType e) {
  Node *cur,*pre=pList;
  pList = pList->next;
  for (cur = pList; cur != NULL && cur->value != e;pre=cur,cur=cur->next)
    ;
  if (cur == NULL) {
    return ERROR;
  } else {
    pre = cur->next;
    free(cur);
  }
  return OK;
}

int main(void) {
  Node *LinkedList = NULL;
  InitList(LinkedList);
  int n = MAX;
  ElemType radElem, e;

  srand((unsigned)time(NULL));
  while (n--) {
    radElem = rand() % 101;
    ListInsert(LinkedList, radElem);
  }

  DisplayList(LinkedList);

  if (IsListEmpty(LinkedList)) {
    cout << "The LinkedList is empty" << endl;
  } else {
    unsigned len = ListLength(LinkedList);
    cout << "The length of LinkedList is " << len << endl;
  }

  if (GetElem(LinkedList, 20, &e) == YES) {
    cout << "The number in 20th position is " << e << endl;
  } else {
    cout << "The length of LinkedList is shortter than 20" << endl;
  }

  int i = LocateElem(LinkedList, 20);
  if (i > 0) {
    cout << "The 20 is already exist in the LinkedList and it is in " << i
         << "th position." << endl;
  } else {
    cout << "The 20 isn`t exist in the LinkedList" << endl;
  }

  ListInsert(LinkedList, 30);
  DisplayList(LinkedList);

  ListDelete(LinkedList, 30);
  DisplayList(LinkedList);

  return 0;
}
#endif

单链表 C++
单链表 C++ 题目 1、创建单链表2、初始化单链表3、释放单链表4、获取单链表中元素的数量5、输出单链表中的所有...
线性表：顺序表和链表
顺序表（数组）优缺点链表优点单链表使用单链表结构单链表初始化单链表初始化单链表建立: 头插法尾插法 ...
单向链表算法
单向链表反转单向链表单链表查找倒数第k个节点单链表递归倒序打印单链表排序单链表删除重复节点
链表基本操作
1、删除单链表节点 2、插入单链表结点单链表具体实现
25_静态单链表的实现
关键词：单链表的一个缺点、静态单链表设计思路、静态单链表的继承层次结构、静态单链表的实现思路、静态单链表的实现 ...
线性表的链式存储-单链表
单链表操作 [x] 单链表的创建（尾插法、头插法） [x] 单链表的查找操作 [x] 单链表的删除操作 [x] 单...
Algorithm小白入门 -- 单链表
单链表递归反转链表k个一组反转链表回文链表 1. 递归反转链表单链表节点的结构如下： 1.1 递归反转整个单链表...
单链表反转
单链表单链表反转递归方法
JavaScript数据结构2——单链表
以下的代码包括了以下几部分单链表初始化单链表的插入单链表的删除单链表的创建（头插法）单链表的创建（尾插法...
链表
链表：通过“指针”将零散的内存块联系起来。常见链表结构：单链表、循环链表和双链表。单链表对比数组学习单链表循...