返回首页
当前位置: 主页 > 编程语言 > C/C++教程 >

用LINKLIST结构体构造非循环单向链表

时间:2015-08-03 23:54来源:电脑教程学习网 www.etwiki.cn 编辑:admin

该例子说明几个问题

    1. 在使用局部变量时,一定要初始化。本例子在InsertList函数中,局部变量i没初始化,程序运行时出错。
    2. printf("%-5d ", p->data);其中%-5d表示变量p->data占5个字符,并且左对齐; %5d表示右对齐。
********************************************************************/
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>

 

 
typedef struct Node
{
  int data;
  struct Node *pNext;
} NODE;

 
typedef struct
{
  NODE *pHead;
  NODE *pTail;
  int len;
} LINKLIST;

 

 
void InitList(LINKLIST *pList)
{
  pList->pHead = pList->pTail = (NODE *)malloc(sizeof(NODE));
  if (pList->pHead == NULL)
  {
    printf("内存分配失败\n");
    exit(-1);
  }
  pList->pTail->pNext = NULL;
  pList->len = 0;

 
  return;
}

 
void CreatList(LINKLIST *pList)
{
  int n;
  int i;

 
  printf("输入链表的长度 len = ");
  scanf("%d", &n);

 
  for (i = 0; i < n; i++)
  {
    NODE *pNew = (NODE *)malloc(sizeof(NODE));
    if (pNew == NULL)
    {
      printf("内存分配失败\n");
      exit(-1);
    }
    pNew->pNext = NULL;

 
    printf("输入链表第 %d 个元素的值: ", i + 1);
    scanf("%d", &pNew->data);
    
    pList->pTail->pNext = pNew;
    pList->pTail = pNew;
    pList->len++;
  }

 
  return;
}

 
void TraverseList(LINKLIST *pList)
{
  NODE *p = pList->pHead->pNext;

 
  while (p != NULL)
  {
    printf("%-5d ", p->data);
    p = p->pNext;
  }
  printf("\n");

 
  return;
}

 
bool ListEmpty(LINKLIST *pList)
{
  if (pList->len == 0)
    return true;
  else
    return false;
}

 
int ListLength(LINKLIST *pList)
{
  return pList->len;
}

 
bool DeleteList(LINKLIST *pList, int pos, int *pVal)
{
  int i = 0;
  NODE *p = pList->pHead;

 
  while ((p->pNext != NULL) && (i < pos - 1))
  {
    i++;
    p = p->pNext;
  }
  
  // 链表为空,返回false
  if ((p->pNext == NULL) || (i > pos - 1))
    return false;

 
  NODE *q = p->pNext;
  *pVal = q->data;
  p->pNext = q->pNext;
  free(q);
  q = NULL;
  pList->len--;

 
  return true;
}

 
bool InsertList(LINKLIST *pList, int pos, int val)
{
  int i = 0;
  NODE *p = pList->pHead;

 
  while ((p != NULL) && (i < pos - 1))
  {
    i++;
    p = p->pNext;
  }

 
  if ((i > pos - 1) || (p == NULL))
    return false;

 
  NODE *pNew = (NODE *)malloc(sizeof(NODE));
  pNew->data = val;
  NODE *q = p->pNext;
  p->pNext = pNew;
  pNew->pNext = q;
  pList->len++;

 
  return true;
}

 
void SortList(LINKLIST *pList)
{
  int i, j, tmp;
  int len = ListLength(pList);
  NODE *p, *q;

 
  for (i = 0, p = pList->pHead->pNext; i < pList->len - 1; i++, p = p->pNext)
  {
    for (j = i + 1, q = p->pNext; j < pList->len; j++, q = q->pNext)
    {
      if (p->data > q->data)    // a[i] > a[j]
      {
        tmp = p->data;     // tmp = a[i];
        p->data = q->data; // a[i] = a[j];
        q->data = tmp;     // a[j] = tmp;
      }
    }
  }

 
  return;
}

 

 

 
int main(void)
{
  int val = 0;
  LINKLIST list;

 
  InitList(&list);
  CreatList(&list);
  
  if (ListEmpty(&list))
  {
    printf("the list is empty\n");
    return 0;
  }
  else
  {
    printf("the list is not empty, the length of list is %d\n", list.len);
    TraverseList(&list);
  }
 
  DeleteList(&list, 3, &val);
  printf("删除链表中第3个元素,该元素是%d\n", val);
  printf("the deleted list is\n");
  TraverseList(&list);
  printf("the length of list is %d\n", list.len);
  
  printf("在链表第3个元素前插入88\n");
  InsertList(&list, 3, 88);
  printf("the inserted list is \n");
  TraverseList(&list);
  printf("the length of list is %d\n", list.len);
  
  printf("the sorted list is \n");
  SortList(&list);
  TraverseList(&list);
  printf("the length of list is %d\n", list.len);

 
  return 0;
}

 

/*********************************************************************
输入链表的长度 len = 7
输入链表第 1 个元素的值: 99
输入链表第 2 个元素的值: -23
输入链表第 3 个元素的值: 52
输入链表第 4 个元素的值: -77
输入链表第 5 个元素的值: 45
输入链表第 6 个元素的值: 38
输入链表第 7 个元素的值: 123
the list is not empty, the length of list is 7
99    -23   52    -77   45    38    123
删除链表中第3个元素,该元素是52
the deleted list is
99    -23   -77   45    38    123
the length of list is 6
在链表第3个元素前插入88
the inserted list is
99    -23   88    -77   45    38    123
the length of list is 7
the sorted list is
-77   -23   38    45    88    99    123
the length of list is 7
Press any key to continue

 

 
输入链表的长度 len = 0
the list is empty
Press any key to continue
*********************************************************************/

 

------分隔线----------------------------
标签(Tag):C语言
------分隔线----------------------------
推荐内容
猜你感兴趣