原创线性链表学习笔记

 2012-6-11 21:31  1653 9 10 分类: MCU/ 嵌入式

这几天学习了单向链表，开始感觉挺难学的，经常出错，而且出一些莫名其妙的错误，其实说白了就是一些内存的问题，当然不是编译问题，是运行起来出的问题，比如有时，链表后面是空了，我还访问就出错。

可是，我最后解决了，但是没有保存记录，也就是没有保存现象和解决方法。

现在把调试好的程序贴上来供大家一起学习！

OPLinkTab.c

#include
#include
#include
#include "DataType.h"

/* 检验链表是否为空 */
UINT CheckLink(Node *head)
{
    HANDLE consolehwnd;
    consolehwnd = GetStdHandle(STD_OUTPUT_HANDLE);
if(NULL == head)
{
  SetConsoleTextAttribute(consolehwnd,FOREGROUND_INTENSITY | FOREGROUND_RED);
  printf("ERR:链表不存在，请先建立！\n");
  return 0;
}
return 1;
}

/* 查找末尾节点 */
Node *FindTail(Node *head,UINT *Len)
{
    Node *ptr = NULL;
ptr = head->Next;
*Len = 0;
while(ptr->Next != NULL)
{
     ptr = ptr->Next;
  *Len =*Len + 1;
}
*Len = *Len + 1;
return ptr;
}

/* 求长度 */
UINT CalcLength(Node *head)
{
UINT Len = 0;
(void *)FindTail(head,&Len);
return Len;
}

/* 打印链表 */
void LinkTab_Print(Node *head)
{
    Node *ptr = NULL;
UINT Len;
Len = CalcLength(head);
if(Len > 200)
{
     printf("Warning:数据长度过限(门限：200)，不予显示，建议直接保存!\n");
  return;
}
if(0 == CheckLink(head)) return;
    if(NULL == head->Next)
{
     printf("Warning:链表无数据!!!\n");
  return;
}
printf("数据：");
ptr = head;
while(ptr->Next != NULL)
{
     ptr = ptr->Next;
  printf("%d ",ptr->Value);
}
printf("\n长度：%d\n",Len);
}

/* 建立单向链表 */
Node *LinkTab_Creat()
{
    Node *head = NULL;
head = (Node *)malloc(sizeof(Node));
head->Next = NULL;
if(head != NULL)
{
     printf("。。。链表成功创建！\n");
  return head;
}
else
{
     printf("。。。链表创建失败！\n");
  return NULL;
}
}

/* 插入一个节点 */
void LinkTab_Insert(Node *head,UINT PolEn)
{
    Node *ptr     = NULL;
Node *NewNode = NULL;
Node *Temp    = NULL;
    UINT Pol    = 0;
UINT PolCnt = 0;
UINT ErrCnt = 0;
UINT Len = 0;

NewNode = (Node *)malloc(sizeof(Node));
printf("请输入数据:");
scanf("%d",&NewNode->Value);
NewNode->Next = NULL;
ptr = FindTail(head,&Len);
if(0 == PolEn)
{
     ptr->Next = NewNode;
  ptr = NewNode;
}
else
{
     printf("请输入插入位置(最大值0~%d):",Len);
  scanf("%d",&Pol);
  ErrCnt = 0;
  while(Pol > Len)
  {
   printf("Warning:超过范围，请重新输入：");
            scanf("%d",&Pol);
            ErrCnt++;
   if(ErrCnt >= MAX_ERR_CNT)
   {
       printf("ERR:超过%d次错误，退出！！！\n",ErrCnt);
    free(NewNode);
    return;
   }
  }
  ptr = head;
  while(PolCnt != Pol)
  {
      ptr = ptr->Next;
   PolCnt++;
  }
  Temp = ptr->Next;
  ptr->Next = NewNode;
  NewNode->Next = Temp;
}
printf("。。。节点插入成功！\n");
}

/* 删除一个节点 */
void LinkTab_Delete(Node *head,UINT PolEn)
{
    Node *ptr     = NULL;
Node *DelNode = NULL;
Node *Temp    = NULL;
UINT Len    = 0;
UINT PolCnt = 0;
UINT Pol    = 0;
UINT ErrCnt = 0;
    ptr = head;
if(NULL == ptr->Next)
{
  printf("头结点不能删除！\n");
  return;
}
while(NULL != ptr->Next)
{
     Temp = ptr;
  ptr = ptr->Next;
  PolCnt++;
}
if(0 == PolEn)
{
     Temp->Next = NULL;
  free(ptr);
}
else
{
     printf("\n请输入删除位置(范围0~%d)",PolCnt-1);
  scanf("%d",&Pol);
  ErrCnt = 0;
  while(Pol >= PolCnt)
  {
   printf("Warning:超过范围，请重新输入：");
            scanf("%d",&Pol);
            ErrCnt++;
   if(ErrCnt >= MAX_ERR_CNT)
   {
       printf("ERR:超过%d次错误，退出！！！\n",ErrCnt);
    return;
   }
  }
  PolCnt = 0;
  ptr = head;
  while(PolCnt <= Pol)
  {
      Temp = ptr;
   ptr = ptr->Next;
   PolCnt++;
  }
  Temp->Next = ptr->Next;
  ptr->Next = NULL;
  free(ptr);
}
    printf("。。。删除成功!\n");
}

/* 查找数据 */
UINT FindData(Node *pHead,UINT Data)
{
    Node *pTemp = NULL;
UINT udPol = 0;
pTemp = pHead->Next;
    while(pTemp->Value != Data)
{
     if(pTemp->Next == NULL)
  {
      return 0xffff;
  }
  pTemp = pTemp->Next;
  udPol++;
}
    return udPol;
}

/* 数组排序 */
void MakeOrder(Node *head)
{
Node *pTemp1 = NULL;
Node *pTemp2 = NULL;
UINT i,j;
UINT udTemp = 0;
UINT Len = 0;
pTemp1 = head->Next;
pTemp2 = head->Next;
FindTail(head,&Len);

while(NULL != pTemp1->Next)
{
     pTemp2= pTemp1;
  while(1)
  {
      pTemp2 = pTemp2->Next;
   if(pTemp1->Value < pTemp2->Value)
   {
       udTemp = pTemp1->Value;
    pTemp1->Value = pTemp2->Value;
                pTemp2->Value = udTemp;
   }
   if(NULL == pTemp2->Next) break;
  }
  pTemp1 = pTemp1->Next;
}
}

/* 生成测试数据 */
Node *MakeTestData(UINT Len)
{
Node *ptr = NULL;
Node *head = NULL;
Node *pNhead = NULL;
UINT i = 0;

head = (Node *)malloc(sizeof(Node));
head->Next = NULL;
pNhead = head;
srand(time(NULL)); /* 产生随机数种子 */
for(i = 1; i < Len; i++)
{
     ptr = (Node *)malloc(sizeof(Node));
  ptr->Value = (rand()%Len) + 1;
  ptr->Next = NULL;

  pNhead->Next = ptr;
  pNhead = ptr;
}
return head;
}

/* 清空链表 */
Node *ClearAllLink(Node *head)
{
    Node *pNhead = NULL;
Node *ptr    = NULL;
    pNhead = head;
ptr = head->Next;
while(pNhead->Next != NULL)
{
     free(pNhead);
  pNhead = ptr;
  ptr = ptr->Next;
}
free(pNhead);
return ptr;
}

/* 保存文件 */
void SaveData(Node *head)
{
    FILE *fp;
Node *pNhead = NULL;
char FileName[10];
    pNhead = head->Next;
printf("请输入文件名：");
scanf("%s",FileName);
strcat(FileName,".dat");
fp = fopen(FileName,"w");
if(fp == NULL)
{
     printf("can not open the file!\n");
  printf("Err:保存文件失败！\n");
  return;
}
while(pNhead->Next != NULL)
{
     fprintf(fp,"%d\n",pNhead->Value);
  pNhead = pNhead->Next;
}
    fprintf(fp,"%d\n",pNhead->Value);
fclose(fp);
printf("文件成功保存到当前目录！\n");
}

LinkTab.c

#include
#include
#include "DataType.h"

void main(void)
{
HANDLE consolehwnd;
char cmd;
Node *DataHead = NULL;
    UINT PolEn = 0;
UINT InData = 0;
UINT Rtn = 0xffff;
UINT Len = 0;
while(1)
{
  consolehwnd = GetStdHandle(STD_OUTPUT_HANDLE);
  SetConsoleTextAttribute(consolehwnd,DEFAULT_COLOR);
  printf("=========================================\n请选择操作：\n");
        printf(" 0：建立链表\n 1：插入节点\n 2：删除节点\n 3：查找数据\n 4：排序\n");
        printf(" 5：打印结果\n 6：生成数据\n 7：清空数据\n 8：保存数据\n 9：退出\n");
  printf("=========================================\n");
  printf("请输入序号：");
        scanf("%s",&cmd);
  switch(cmd)
  {
  case '0':
           if(DataHead != NULL)
     {
      printf("Err:链表已存在，要重新建立请先删除!\n");
      break;
     }
     DataHead = LinkTab_Creat();
     break;
  case '1':
       if(0 == CheckLink(DataHead))break;
    printf("是否指定位置(0：不指定，1：指定)：");
    scanf("%d",&PolEn);
    LinkTab_Insert(DataHead,PolEn);
    break;
  case '2':
       if(0 == CheckLink(DataHead))break;
    printf("是否指定位置(0：不指定，1：指定)：");
    scanf("%d",&PolEn);
       LinkTab_Delete(DataHead,PolEn);
       break;
  case '3':
       if(0 == CheckLink(DataHead))break;
    printf("请输入要查找的数据：");
    scanf("%d",&InData);
       Rtn = FindData(DataHead,InData);
    if(0xffff == Rtn)
    {
        printf("Warning:数据未找到！\n");
     break;
    }
    printf("数据在第%d位\n",Rtn);
       break;
  case '4':
       if(0 == CheckLink(DataHead))break;
    MakeOrder(DataHead);
    if(CalcLength(DataHead) < 200)
    {
                    LinkTab_Print(DataHead);
    }
    printf("...排序完成！\n");
       break;
  case '5':
       if(0 == CheckLink(DataHead))break;
       LinkTab_Print(DataHead);
    break;
  case '6':
           if(DataHead != NULL)
     {
      printf("Err:链表已存在，要重新建立请先删除!\n");
      break;
     }
    printf("请输入测试数据的长度：");
    scanf("%d",&Len);
                DataHead = MakeTestData(Len);
    if(DataHead != NULL)
    {
           if(CalcLength(DataHead) < 200)
     {
      LinkTab_Print(DataHead);
     }
        printf("测试数据成功生成！\n");
    }
    else
    {
         printf("测试数据失败！\n");
    }
       break;
  case '7':
       if(0 == CheckLink(DataHead))break;
    DataHead = ClearAllLink(DataHead);
       if(DataHead == NULL)
    {
        printf("清除成功！\n");
    }
    else
    {
        printf("清除失败！\n");
    }
       break;
  case '8':
       if(0 == CheckLink(DataHead))break;
    SaveData(DataHead);
       break;
  case '9':
       exit(0);

  default:
       consolehwnd = GetStdHandle(STD_OUTPUT_HANDLE);
    SetConsoleTextAttribute(consolehwnd,FOREGROUND_INTENSITY | FOREGROUND_RED);
    printf("ERR:命令不存在！\n");
    break;
  }
}
}

链表