第4周学习进度表

周数	专业目标学习	专业学习时间	博客发表量	人文方面的学习	知识技能总结
4	数据结构与算法，HTML，计算机网络基础	平均3小时/天	3	《世界是数字的》	数据结构：这周学习了一种比顺序表更利于插入和删除的单链表，代码只是参考老师的敲出来的，我认为只有从空白的界面开始写，才会对自己有帮助，希望自己能坚持反复的敲代码。

新增代码量：

#include "stdafx.h"
#include <stdlib.h>
#include <stdio.h>
typedef int DataType;

typedef struct LNode
{
DataType data; /*存储结点值*/
LNode *next; /*链表下一结点的地址*/
}LNode,*LinkList;

/*1.初始化链表函数,返回带头结点的单链表的头指针*/
struct LNode * InitList()
{
struct LNode *pHead=(struct LNode *) malloc(sizeof(LNode));//为链表的头指针分配内存空间
if(pHead!=NULL)
pHead->next=NULL;
return pHead;
}

/*在带头结点的单链表中,查找第i(1≤i≤n)个结点，如果找到,则返回该结点的存储位置，否则返回NULL */
LNode *Locate(LNode *head,int i)
{
int k;
LNode *p=head;
for(k=0;k<i;k++){
if(p==NULL)
return NULL;
p=p->next; //移动指针
}
return p;
}

//在第i个节点之前添加数据y，成功添加返回该节点的指针，否则返回空
struct LNode *InsertNode(struct LNode *head,int i,DataType y)
{
struct LNode *p=Locate(head,i-1);//先获取在第i个节点之前的指针
struct LNode *s;
if(p!=NULL)
{
s=(LNode *) malloc(sizeof(LNode));//分配新节点的内存空间
if(s==NULL)
return NULL;
s->data=y;
s->next=p->next; //添加数据
p->next=s;
}
return p;
}

//删除第i个节点的数据，成功删除返回1，否则返回-1
int DelNode(LNode *head,int i)
{
LNode *p=head,*q;
int j=1;
if(i<1)
{
printf("删除的位置不合法。删除失败！");
exit(1);

}
while(p->next!=NULL&&j<i)
{
p=p->next;
j++;

}
if(j!=i)
{
printf("DeLink函数执行，i值超过链表长度，删除失败\n");
return -1;
}
else
{
q=p->next;
p->next=q->next;
printf("删除第%d个结点成功，删除的结点值是%d\n",i,q->data);
free(q);
}
//添加代码
return 1;
}

//在第i个节点之后添加数据y，成功添加返回该节点的指针，否则返回空
struct LNode *InsertNodeAfter(struct LNode *head,int i,DataType y)
{ struct LNode *p=Locate(head,i);//先获取第i个节点的指针
struct LNode *s;
if(p!=NULL)
{
s=(LNode *) malloc(sizeof(LNode));//分配新节点的内存空间
if(s==NULL)
return NULL;
s->data=y;
s->next=p->next; //添加数据
p->next=s;
}

return s;
//添加代码
}

/*在带头结点的单链表中,查找按指定值等于key的结点，如果找到返回该值顺序位置，否则返回-1 缺陷，修改*/
int LocateKey(LNode *pHead, DataType key)
{
int n=0;
LNode *p=pHead;
while(p!=NULL)
{
p=p->next;
if(p->data==key)
{
printf("80的位置在第%d个\n",n+1);
return n+1;
}
n++;
}
return -1;
}

/*在带头结点的单链表中，获取第i个节点的数据保存到y中，如果成功获取返回1，否则返回0*/
int GetData(LNode *head, int i,DataType &y)
{
int count=0;
if(i<=0)
{
printf("Locate函数执行，i值非法\n");
return NULL;

}//添加代码
return 1;

while(head->next!=NULL)
{
if(count<i)
{
++count;
head=head->next;
}
else
break;
}
if(i==count)
{
head->data=y;
return 1;

}
else
return 0;
}
//打印输出链表的每一个节点的数据值
void PrintList(LNode *pHead)
{
int n=0;
if(pHead==NULL) return;
LNode *p=pHead->next;
while(p!=NULL){
printf("%d ",p->data);
n++;
p=p->next;
}
printf(" length=%d\n",n);
}

int main(int argc, char* argv[])
{ //验证

LNode *head=InitList(); //获取带头结点的单链表的头指针

int a[]={54,89,13,9,79,88,32,70,44,7},i;
for(i=0;i<10;i++)
{
InsertNode(head,i+1,a[i]);
}

DataType y;
PrintList(head);
InsertNode(head,2,80);
PrintList(head);
DelNode(head,4);
PrintList(head);
InsertNodeAfter(head,2,55);
PrintList(head);

int nn= LocateKey(head,80);

PrintList(head);

return 0;
}

第4周学习进度表

推荐阅读