线性结构
线性结构主要包括线性表、栈和队列。
线性表可以分成由数组实现的顺序表和由指针实现的链式表。
- 线性表： 逻辑结构， 就是对外暴露数据之间的关系，不关心底层如何实现，数据结构的逻辑结构大分类就是线性结构和非线性结构而顺序表、链表都是一种线性表。
- 顺序表、链表： 物理结构，他是实现一个结构实际物理地址上的结构。比如顺序表就是用数组实现。而链表用指针完成主要工作。不同的结构在不同的场景有不同的区别。
链表
单链表功能实现详细版
创建、插入、删除
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int ElementType;
typedef struct Node
{
ElementType Data;
struct Node *Next;
}NODE,*LIST,*LPNODE;
LIST createHead();
LPNODE createNode(ElementType X);
void insertByHead(LIST headNode, ElementType X);
void insertByBack(LIST headNode, ElementType X);
void insertByAppoin(LIST headNode, ElementType X, int posData);
void deleteByHead(LIST headNode);
void deleteByBack(LIST headNode);
void deleteByAppoin(LIST headNode, int posData);
void printList(LIST headNode);
void freeList(LIST* headNode);
LIST createHead()
{
LIST headNode = (LIST)malloc(sizeof(struct Node));
assert(headNode);
headNode->Next = NULL;
return headNode;
}
LPNODE createNode(ElementType X)
{
LPNODE newNode = (LPNODE)malloc(sizeof(NODE));
assert(newNode);
newNode->Data = X;
newNode->Next = NULL;
return newNode;
}
void InsertByHead(LIST headNode, ElementType X)
{
LPNODE newNode = createNode(X);
newNode->Next = headNode->Next;
headNode->Next = newNode;
}
void insertByBack(LIST headNode, ElementType X)
{
LPNODE pMove = headNode;
while(pMove->Next)
pMove = pMove->Next;
LPNODE newNode = createNode(X);
pMove->Next = newNode;
}
void insertByAppoin(LIST headNode, ElementType X, int posData)
{
LPNODE posLeftNode = headNode;
LPNODE posNode = headNode->Next;
while(posNode != NULL && posData != posNode->Data)
{
posLeftNode = posNode;
posNode = posNode->Next;
}
if(!posNode)
printf("未找到，无法做指定数据所在的位置插入！\n");
else
{
LPNODE newNode = createNode(X);
newNode->Next = posNode;
posLeftNode->Next = newNode;
//这里可以不考虑顺序
}
}
void deleteByHead(LIST headNode)
{
LPNODE temp = headNode->Next;
if(!temp)
printf("链表为空，无法删除！\n");
else
{
headNode->Next = temp->Next;
free(temp);
}
}
void deleteByBack(LIST headNode)
{
LPNODE pTailLeft = headNode;
LPNODE pTail = headNode->Next;
while(pTail != NULL && pTail->Next != NULL)
{
pTailLeft = pTail;
pTail = pTail->Next;
}
if(pTail == NULL)
printf("链表为空，无法删除！\n");
else
{
free(pTail);
pTailLeft->Next = NULL;
}
}
void deleteByAppoin(LIST headNode, int posData)
{
LPNODE posLeftNode = headNode;
LPNODE posNode = headNode->Next;
while(posNode && posNode->Data != posData)
{
posLeftNode = posNode;
posNode = posNode->Next;
}
if(!posNode)
printf("无法删除指定数据！\n");
else
{
posLeftNode->Next = posNode->Next;
free(posNode);
posNode = NULL;
}
}
void printList(LIST headNode)
{
if(headNode == NULL)
{
printf("无法打印链表，链表为空！\n");
return;
}
LPNODE pMove = headNode->Next;
while(pMove != NULL)
{
printf("%d ",pMove->Data);
pMove = pMove->Next;
}
printf("\n");
}
void freeList(LIST* headNode)
{
if(headNode == NULL) //写成if((*headNode) == NULL)也行
return;
LPNODE nextNode = NULL;
while((*headNode) != NULL)
{
nextNode = (*headNode)->Next;
free(*headNode);
*headNode = nextNode;
}
}
int main()
{
LIST list = createHead();
InsertByHead(list,1);
InsertByHead(list,2);
InsertByHead(list,3);
InsertByHead(list,4);
InsertByHead(list,5);
printList(list);
insertByBack(list,5);
insertByBack(list,4);
insertByBack(list,3);
printList(list);
insertByAppoin(list,6,2);
insertByAppoin(list,7,2);
printList(list);
deleteByHead(list);
deleteByBack(list);
deleteByAppoin(list,2);
printList(list);
freeList(&list);
printList(list);
return 0;
}
5 4 3 2 1
5 4 3 2 1 5 4 3
5 4 3 6 7 2 1 5 4 3
4 3 6 7 1 5 4
无法打印链表，链表为空！
合并、反转
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int ElementType;
typedef struct Node
{
ElementType Data;
struct Node *Next;
}NODE,*LIST,*LPNODE;
LIST createHead();
LPNODE createNode(ElementType X);
void insertByHead(LIST headNode, ElementType X);
void insertByBack(LIST headNode, ElementType X);
void printList(LIST headNode);
LIST createHead()
{
LIST headNode = (LIST)malloc(sizeof(struct Node));
assert(headNode);
headNode->Next = NULL;
return headNode;
}
LPNODE createNode(ElementType X)
{
LPNODE newNode = (LPNODE)malloc(sizeof(NODE));
assert(newNode);
newNode->Data = X;
newNode->Next = NULL;
return newNode;
}
void InsertByHead(LIST headNode, ElementType X)
{
LPNODE newNode = createNode(X);
newNode->Next = headNode->Next;
headNode->Next = newNode;
}
void insertByBack(LIST headNode, ElementType X)
{
LPNODE pMove = headNode;
while(pMove->Next)
pMove = pMove->Next;
LPNODE newNode = createNode(X);
pMove->Next = newNode;
}
void printList(LIST headNode)
{
if(headNode == NULL)
{
printf("无法打印链表，链表为空！\n");
return;
}
LPNODE pMove = headNode->Next;
while(pMove != NULL)
{
printf("%d ",pMove->Data);
pMove = pMove->Next;
}
printf("\n");
}
void freeList(LIST* headNode)
{
if(headNode == NULL) //写成if((*headNode) == NULL)也行
return;
LPNODE nextNode = NULL;
while((*headNode) != NULL)
{
nextNode = (*headNode)->Next;
free(*headNode);
*headNode = nextNode;
}
}
LIST listCat(LIST list1, LIST list2) //把list2加到list1的末尾。
{
if(list1->Next == NULL || list2->Next == NULL)
return (list1->Next == NULL) ? list2 : list1;
LPNODE pMove = list1;
while(pMove->Next)
{
pMove = pMove->Next;
}
pMove->Next = list2->Next;
return list1;
}
LIST listCatByBack(LIST list1, LIST list2) //把list2加到list1的末尾。这里使用尾插法
{
LPNODE pMove = list2->Next;
while(pMove != NULL)
{
insertByBack(list1,pMove->Data);
pMove = pMove->Next;
}
return list1;
}
LIST listCatByValue(LIST list1, LIST list2)
{
LIST list3 = createHead();
LPNODE pFirst = list1->Next;
while(pFirst)
{
LPNODE pSecond = list2->Next;
while(pSecond)
{
if(pFirst->Data == pSecond->Data)
{
insertByBack(list3,pFirst->Data);
break;
}
pSecond = pSecond->Next;
}
pFirst = pFirst->Next;
}
return list3;
}
void ListReverseFirst(LIST* list)
{
LIST new_list = createHead();
LPNODE pMove = (*list)->Next;
while(pMove)
{
InsertByHead(new_list, pMove->Data);
pMove = pMove->Next;
}
freeList(list);
*list = new_list;
}
LIST ListReverse1(LIST list)
{
LIST new_list = createHead();
LPNODE pMove = list->Next;
while(pMove)
{
InsertByHead(new_list, pMove->Data);
pMove = pMove->Next;
}
return new_list;
}
void ListReverse2(LIST list)
{
LPNODE pre = NULL;
LPNODE cur = list->Next;
LPNODE nextNode = list->Next;
while(cur)
{
//先存储下一个，再反转
nextNode = cur->Next;
cur->Next = pre;
pre = cur;
cur = nextNode;
}
list->Next = pre;
}
int main()
{
LIST list1 = createHead();
InsertByHead(list1,4);
InsertByHead(list1,2);
InsertByHead(list1,1);
printList(list1);
LIST list2 =createHead();
InsertByHead(list2,4);
InsertByHead(list2,2);
printList(list2);
//LIST list3 = listCat(list1,list2);
//printList(list3);
//ListReverseFirst(&list1);
//printList(list1);
ListReverse2(list1);
printList(list1);
return 0;
}
1 2 4
2 4
4 2 1
有序链表
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int ElementType;
typedef struct Node
{
ElementType Data;
struct Node *Next;
}NODE,*LIST,*LPNODE;
LIST createHead()
{
LIST headNode = (LIST)malloc(sizeof(struct Node));
assert(headNode);
headNode->Next = NULL;
return headNode;
}
LPNODE createNode(ElementType X)
{
LPNODE newNode = (LPNODE)malloc(sizeof(NODE));
assert(newNode);
newNode->Data = X;
newNode->Next = NULL;
return newNode;
}
void InsertBySort(LIST headNode, ElementType X)
{
LPNODE newNode = createNode(X);
LPNODE preNode = headNode;
LPNODE posNode = headNode->Next;
while(posNode != NULL && posNode->Data < X)
{
preNode = posNode;
posNode = posNode->Next;
}
if(posNode == NULL)
{
preNode->Next = newNode;
}
else
{
preNode->Next = newNode;
newNode->Next = posNode;
}
}
void printList(LIST headNode)
{
if(headNode == NULL)
{
printf("无法打印链表，链表为空！\n");
return;
}
LPNODE pMove = headNode->Next;
while(pMove != NULL)
{
printf("%d ",pMove->Data);
pMove = pMove->Next;
}
printf("\n");
}
int main()
{
LIST list3 = createHead();
InsertBySort(list3,4);
InsertBySort(list3,5);
InsertBySort(list3,1);
InsertBySort(list3,40);
InsertBySort(list3,53);
InsertBySort(list3,12);
InsertBySort(list3,49);
InsertBySort(list3,25);
InsertBySort(list3,19);
printList(list3);
return 0;
}
1 2 4
2 4
1 4 5 12 19 25 40 49 53
无头单链表
核心在于表头的处理，插入操作需要使用二级指针来修改头指针。要考虑链表为空的状态。
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int ElementType;
struct Node
{
ElementType Data;
struct Node *Next;
};
struct Node* createNode(ElementType X)
{
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
assert(newNode);
newNode->Data = X;
newNode->Next = NULL;
return newNode;
}
void InsertByHead(struct Node** headNode, ElementType X)
{
struct Node* newNode = createNode(X);
newNode->Next = *headNode;
*headNode = newNode;
}
void InsertByBack(struct Node** headNode, ElementType X)
{
if(headNode == NULL)
{
InsertByHead(headNode,X);
}
else
{
struct Node* pMove = *headNode;
while(pMove->Next)
{
pMove = pMove->Next;
}
struct Node* newNode = createNode(X);
pMove->Next = newNode;
}
}
void printList(struct Node* headNode)
{
struct Node* pMove = headNode;
while(pMove != NULL)
{
printf("%d ",pMove->Data);
pMove = pMove->Next;
}
printf("\n");
}
int main()
{
struct Node* list3 = NULL;
InsertByHead(&list3,4);
InsertByHead(&list3,5);
InsertByHead(&list3,1);
InsertByHead(&list3,40);
printList(list3);
printf("\n");
InsertByBack(&list3,53);
InsertByBack(&list3,12);
InsertByBack(&list3,49);
InsertByBack(&list3,25);
InsertByBack(&list3,19);
printList(list3);
return 0;
}
40 1 5 4
40 1 5 4 53 12 49 25 19
双向链表
普通双向链表
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef struct Node *LPNODE;
typedef int ElementType;
struct Node
{
LPNODE prev;
LPNODE next;
ElementType data;
};
LPNODE createNode(ElementType data)
{
LPNODE newNode = (LPNODE)malloc((sizeof(struct Node)));
assert(newNode);
newNode->prev = NULL;
newNode->next = NULL;
newNode->data = data;
return newNode;
}
//再封装的方式描述链表特性
struct List
{
LPNODE firstNode;
LPNODE lastNode;
int listSize;
};
//创建链表，描述链表的初始状态
struct List* creatList()
{
struct List* list = (struct List*)malloc(sizeof(struct List));
//assert(list);
//这里也可以写成if语句形式
if(list == NULL)
return NULL;
list->firstNode = NULL;
list->lastNode = NULL;
list->listSize = 0;
return list;
}
//表头插入
void InsertByHead(struct List* list, ElementType data)
{
LPNODE newNode = createNode(data);
if(list->listSize == 0)
{
//第一次插入
list->firstNode = newNode;
list->lastNode = newNode;
list->listSize++;
}
else
{
newNode->next = list->firstNode;
list->firstNode->prev = newNode;
list->firstNode = newNode;
list->listSize++;
}
}
void printListByHead(struct List* list)
{
LPNODE pMove = list->firstNode;
while(pMove)
{
printf("%d\t",pMove->data);
pMove = pMove->next;
}
printf("\n");
}
void printListByRear(struct List* list)
{
LPNODE pMove = list->lastNode;
while(pMove)
{
printf("%d\t",pMove->data);
pMove = pMove->prev;
}
printf("\n");
}
int main()
{
struct List* list = creatList();
for(int i=0; i<5; i++)
InsertByHead(list, i);
printListByHead(list);
printListByRear(list);
}
4 3 2 1 0
0 1 2 3 4
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef struct Node *LPNODE;
typedef int ElementType;
struct Node
{
LPNODE prev;
LPNODE next;
ElementType data;
};
LPNODE createNode(ElementType data)
{
LPNODE newNode = (LPNODE)malloc((sizeof(struct Node)));
assert(newNode);
newNode->prev = NULL;
newNode->next = NULL;
newNode->data = data;
return newNode;
}
//再封装的方式描述链表特性
struct List
{
LPNODE firstNode;
LPNODE lastNode;
int listSize;
};
//创建链表，描述链表的初始状态
struct List* creatList()
{
struct List* list = (struct List*)malloc(sizeof(struct List));
//assert(list);
//这里也可以写成if语句形式
if(list == NULL)
return NULL;
list->firstNode = NULL;
list->lastNode = NULL;
list->listSize = 0;
return list;
}
//表头插入
void InsertByHead(struct List* list, ElementType data)
{
LPNODE newNode = createNode(data);
if(list->listSize == 0)
{
list->firstNode = newNode;
list->lastNode = newNode;
list->listSize++;
}
else
{
newNode->next = list->firstNode;
list->firstNode->prev = newNode;
list->firstNode = newNode;
list->listSize++;
}
}
//表尾插入
void InsertByTail(struct List* list, ElementType data)
{
LPNODE newNode = createNode(data);
if(list->listSize == 0)
{
list->firstNode = newNode;
list->lastNode = newNode;
list->listSize++;
}
else
{
newNode->prev = list->lastNode;
list->lastNode->next = newNode;
list->lastNode = newNode;
list->listSize++;
}
}
//指定数据处插入方式1
void InsertByAppointment(struct List* list, ElementType data, ElementType posData)
{
LPNODE pos = list->firstNode;
LPNODE preNode = NULL;
while(pos != NULL && pos->data != posData)
{
preNode = pos;
pos = pos->next;
}
if(pos == NULL)
{
printf("Failed! There is no posData in this linked list!\n");
}
else if(pos == list->firstNode)
{
//指定位置为第一个结点，这时使用头插法
InsertByHead(list,data);
}
else
{
LPNODE newNode = createNode(data);
preNode->next = newNode;
newNode->prev = preNode;
newNode->next = pos;
pos->prev = newNode;
list->listSize++;
}
}
void DeleteByHead(struct List* list)
{
if(list->listSize == 0)
{
printf("The linked list is empty!\n");
return;
}
LPNODE nextNode = list->firstNode->next;
free(list->firstNode);
list->firstNode = nextNode;
if(list->listSize == 1)
list->lastNode = NULL;
else
nextNode->prev = NULL;
list->listSize--;
}
void DeleteByTail(struct List* list)
{
if(list->listSize == 0)
{
printf("The linked list is empty!\n");
return;
}
LPNODE prevNode = list->lastNode->prev;
free(list->lastNode);
list->lastNode = prevNode;
if(list->listSize == 1)
list->firstNode = NULL;
else
prevNode->next = NULL;
list->listSize--;
}
int IsEmpty(struct List* list)
{
return list->listSize == 0;
}
void printListByHead(struct List* list)
{
LPNODE pMove = list->firstNode;
while(pMove)
{
printf("%d\t",pMove->data);
pMove = pMove->next;
}
printf("\n");
}
void printListByRear(struct List* list)
{
LPNODE pMove = list->lastNode;
while(pMove)
{
printf("%d\t",pMove->data);
pMove = pMove->prev;
}
printf("\n");
}
int main()
{
struct List* list = creatList();
for(int i=0; i<5; i++)
InsertByHead(list, i);
printListByHead(list);
printListByRear(list);
DeleteByHead(list);
printListByHead(list);
printListByRear(list);
for(int i=0; i<5; i++)
InsertByTail(list, i);
printListByHead(list);
printListByRear(list);
InsertByAppointment(list,100,4);
printListByRear(list);
InsertByAppointment(list,100,2);
InsertByTail(list,30);
printListByRear(list);
InsertByAppointment(list,200,30);
printListByHead(list);
printListByRear(list);
while(!IsEmpty(list))
{
DeleteByTail(list);
printListByHead(list);
printListByRear(list);
}
}
4 3 2 1 0
0 1 2 3 4
3 2 1 0
0 1 2 3
3 2 1 0 0 1 2 3 4
4 3 2 1 0 0 1 2 3
4 100 3 2 1 0 0 1 2 3
30 4 100 3 2 1 0 0 1 2 100 3
3 100 2 1 0 0 1 2 3 100 4 200 30
30 200 4 100 3 2 1 0 0 1 2 100 3
3 100 2 1 0 0 1 2 3 100 4 200
200 4 100 3 2 1 0 0 1 2 100 3
3 100 2 1 0 0 1 2 3 100 4
4 100 3 2 1 0 0 1 2 100 3
3 100 2 1 0 0 1 2 3 100
100 3 2 1 0 0 1 2 100 3
3 100 2 1 0 0 1 2 3
3 2 1 0 0 1 2 100 3
3 100 2 1 0 0 1 2
2 1 0 0 1 2 100 3
3 100 2 1 0 0 1
1 0 0 1 2 100 3
3 100 2 1 0 0
0 0 1 2 100 3
3 100 2 1 0
0 1 2 100 3
3 100 2 1
1 2 100 3
3 100 2
2 100 3
3 100
100 3
3
3
指定位置删除需要特殊处理头和尾。。。
双向循环链表
注意：这里最好写有头（头节点不存数据即可）的双向循环链表。。
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef struct Node *LPNODE;
typedef int ElementType;
struct Node
{
LPNODE prev;
LPNODE next;
ElementType data;
};
LPNODE createNode(ElementType data)
{
//新节点不需要是环形
LPNODE newNode = (LPNODE)malloc((sizeof(struct Node)));
assert(newNode);
newNode->prev = NULL;
newNode->next = NULL;
newNode->data = data;
return newNode;
}
//创建链表，描述链表的初始状态
struct Node* creatList()
{
//单个节点指向自身，形成环形
struct Node* headNode = (struct Node*)malloc(sizeof(struct Node));
//assert(list);
//这里也可以写成if语句形式
if(headNode == NULL)
return NULL;
headNode->prev = headNode;
headNode->next = headNode;
return headNode;
}
//表尾插入
void InsertByTail(struct Node* headNode, ElementType data)
{
LPNODE newNode = createNode(data);
LPNODE temp = headNode->prev;
//headNode->prev是最后一个结点
newNode->next = headNode;
headNode->prev = newNode;
temp->next = newNode;
newNode->prev = temp;
}
void InsertByAppointment(struct Node* headNode, ElementType data, ElementType posData)
{
LPNODE preNode = headNode;
LPNODE posNode = headNode->next;
while(headNode != posNode && posData != posNode->data)
{
preNode = posNode;
posNode = posNode->next;
}
if(headNode == posNode)
{
printf("The posData is not in this linked list!\n");
return;
}
else
{
LPNODE newNode = createNode(data);
newNode->next = posNode;
posNode->prev = newNode;
preNode->next = newNode;
newNode->prev = preNode;
}
}
void printListByHead(struct Node* headNode)
{
LPNODE pMove = headNode->next;
while(pMove != headNode)
{
printf("%d\t",pMove->data);
pMove = pMove->next;
}
printf("\n");
}
void printListByTail(struct Node* headNode)
{
LPNODE pMove = headNode->prev;
while(pMove != headNode)
{
printf("%d\t",pMove->data);
pMove = pMove->prev;
}
printf("\n");
}
int main()
{
struct Node* list = creatList();
for(int i=0; i<5; i++)
InsertByTail(list, i);
printListByHead(list);
printListByTail(list);
InsertByAppointment(list, 100, 2);
printListByHead(list);
printListByTail(list);
return 0;
}
0 1 2 3 4
4 3 2 1 0
0 1 100 2 3 4
4 3 2 100 1 0
单链表题目
PTA6-1 单链表逆转
本题要求实现一个函数，将给定的单链表逆转。
函数接口定义：
List Reverse( List L );
其中List结构定义如下：
typedef struct Node *PtrToNode;
struct Node {
ElementType Data; /* 存储结点数据 */
PtrToNode Next; /* 指向下一个结点的指针 */
};
typedef PtrToNode List; /* 定义单链表类型 */
L是给定单链表，函数Reverse要返回被逆转后的链表。
裁判测试程序样例：
#include <stdio.h>
#include <stdlib.h>
typedef int ElementType;
typedef struct Node *PtrToNode;
struct Node {
ElementType Data;
PtrToNode Next;
};
typedef PtrToNode List;
List Read(); /* 细节在此不表 */
void Print( List L ); /* 细节在此不表 */
List Reverse( List L );
int main()
{
List L1, L2;
L1 = Read();
L2 = Reverse(L1);
Print(L1);
Print(L2);
return 0;
}
/* 你的代码将被嵌在这里 */
输入样例：
5
1 3 4 5 2
输出样例：
1
2 5 4 3 1
双指针解法：
List Reverse( List L )
{
List cur = L;
List pre = NULL;
while(cur!=NULL)
{
List temp = cur->Next;
cur->Next = pre;
pre = cur;
cur = temp;
}
return pre;
}
递归解法：
List Reverse( List L )
{
if(L==NULL||L->Next==NULL)
return L;
List cur = Reverse(L->Next);
L->Next->Next=L;
L->Next=NULL;
return cur;
}
PTA 6-2 顺序表操作集
本题要求实现顺序表的操作集。
函数接口定义：
List MakeEmpty();
Position Find( List L, ElementType X );
bool Insert( List L, ElementType X, Position P );
bool Delete( List L, Position P );
其中List结构定义如下：
typedef int Position;
typedef struct LNode *List;
struct LNode {
ElementType Data[MAXSIZE];
Position Last; /* 保存线性表中最后一个元素的位置 */
};
各个操作函数的定义为：
List MakeEmpty()：创建并返回一个空的线性表；
Position Find( List L, ElementType X )：返回线性表中X的位置。若找不到则返回ERROR；
bool Insert( List L, ElementType X, Position P )：将X插入在位置P并返回true。若空间已满，则打印“FULL”并返回false；如果参数P指向非法位置，则打印“ILLEGAL POSITION”并返回false；
bool Delete( List L, Position P )：将位置P的元素删除并返回true。若参数P指向非法位置，则打印“POSITION P EMPTY”（其中P是参数值）并返回false。
裁判测试程序样例：
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 5
#define ERROR -1
typedef enum {false, true} bool;
typedef int ElementType;
typedef int Position;
typedef struct LNode *List;
struct LNode {
ElementType Data[MAXSIZE];
Position Last; /* 保存线性表中最后一个元素的位置 */
};
List MakeEmpty();
Position Find( List L, ElementType X );
bool Insert( List L, ElementType X, Position P );
bool Delete( List L, Position P );
int main()
{
List L;
ElementType X;
Position P;
int N;
L = MakeEmpty();
scanf("%d", &N);
while ( N-- ) {
scanf("%d", &X);
if ( Insert(L, X, 0)==false )
printf(" Insertion Error: %d is not in.\n", X);
}
scanf("%d", &N);
while ( N-- ) {
scanf("%d", &X);
P = Find(L, X);
if ( P == ERROR )
printf("Finding Error: %d is not in.\n", X);
else
printf("%d is at position %d.\n", X, P);
}
scanf("%d", &N);
while ( N-- ) {
scanf("%d", &P);
if ( Delete(L, P)==false )
printf(" Deletion Error.\n");
if ( Insert(L, 0, P)==false )
printf(" Insertion Error: 0 is not in.\n");
}
return 0;
}
/* 你的代码将被嵌在这里 */
输入样例：
6
1 2 3 4 5 6
3
6 5 1
2
-1 6
输出样例：
FULL Insertion Error: 6 is not in.
Finding Error: 6 is not in.
5 is at position 0.
1 is at position 4.
POSITION -1 EMPTY Deletion Error.
FULL Insertion Error: 0 is not in.
POSITION 6 EMPTY Deletion Error.
FULL Insertion Error: 0 is not in.
List MakeEmpty()
{
List PtrL;
PtrL=(List)malloc(sizeof(struct LNode));
PtrL->Last=-1;
return PtrL;
}
Position Find( List L, ElementType X )
{
for(Position i=0;i<=L->Last+1;i++)
{
if(L->Data[i]==X)
return i;
}
return ERROR;
/*int i=0;
while(i<L->Last&&L->Data[i]!=X)
i++;
if(i>L->Last) return ERROR;//如果没找到，返回ERROR
else return i;//找到后返回的是存储位置*/
}
bool Insert( List L, ElementType X, Position P )
{
if(L->Last==MAXSIZE-1)
{
printf("FULL");
return false;
}
if(P<0||P>L->Last+1||P>=MAXSIZE)
{
printf("ILLEGAL POSITION");
return false;
}
for(int j=L->Last;j>=P;j--)
{
L->Data[j+1]=L->Data[j];
}
L->Data[P]=X;
L->Last++;
return true;
}
bool Delete( List L, Position P )
{
if(P<0||P>L->Last)
{
printf("POSITION %d EMPTY",P);
return false;
}
if(P!=L->Last)
{
for(int j=P;j<L->Last;j++)
L->Data[j]=L->Data[j+1];
}
L->Last--;
return true;
}
PTA 6-3 求链式表的表长
本题要求实现一个函数，求链式表的表长。
函数接口定义：
int Length( List L );
其中List结构定义如下：
typedef struct LNode *PtrToLNode;
struct LNode {
ElementType Data;
PtrToLNode Next;
};
typedef PtrToLNode List;
L是给定单链表，函数Length要返回链式表的长度。
裁判测试程序样例：
#include <stdio.h>
#include <stdlib.h>
typedef int ElementType;
typedef struct LNode *PtrToLNode;
struct LNode {
ElementType Data;
PtrToLNode Next;
};
typedef PtrToLNode List;
List Read(); /* 细节在此不表 */
int Length( List L );
int main()
{
List L = Read();
printf("%d\n", Length(L));
return 0;
}
/* 你的代码将被嵌在这里 */
输入样例：
1 3 4 5 2 -1
输出样例：
5
int Length( List L )
{
List head=L;
int length=0;
while(head!=NULL)
{
length++;
head=head->Next;
}
return length;
}
PTA 6-4 链式表的按序号查找
本题要求实现一个函数，找到并返回链式表的第K个元素。
函数接口定义：
ElementType FindKth( List L, int K );
其中List结构定义如下：
typedef struct LNode *PtrToLNode;
struct LNode {
ElementType Data;
PtrToLNode Next;
};
typedef PtrToLNode List;
L是给定单链表，函数FindKth要返回链式表的第K个元素。如果该元素不存在，则返回ERROR。
裁判测试程序样例：
#include <stdio.h>
#include <stdlib.h>
#define ERROR -1
typedef int ElementType;
typedef struct LNode *PtrToLNode;
struct LNode {
ElementType Data;
PtrToLNode Next;
};
typedef PtrToLNode List;
List Read(); /* 细节在此不表 */
ElementType FindKth( List L, int K );
int main()
{
int N, K;
ElementType X;
List L = Read();
scanf("%d", &N);
while ( N-- ) {
scanf("%d", &K);
X = FindKth(L, K);
if ( X!= ERROR )
printf("%d ", X);
else
printf("NA ");
}
return 0;
}
/* 你的代码将被嵌在这里 */
输入样例：
1 3 4 5 2 -1
6
3 6 1 5 4 2
输出样例：
4 NA 1 2 5 3
ElementType FindKth( List L, int K )
{
List p = L;
if(p==NULL)
return ERROR;
int i = 1;
while(p!=NULL && i<K)
{
p=p->Next;
i++;
}
if(i==K)
return p->Data;
else return ERROR;
}
这样写会在测试题中数据时报错段错误，这是if(i==K)这个判断条件不严谨导致的。
设想一下K=2; L的长度仅为1，这个程序会进入while循环，然后i=2，但此时p结点对应的Data不存在。这时输出会报错段错误。修改后能AC的代码如下：
ElementType FindKth( List L, int K )
{
List p = L;
int i = 1;
if(p==NULL)
return ERROR;
else
{
while(p!=NULL && i<K)
{
p=p->Next;
i++;
}
if(p!=NULL && i==K)
return p->Data;
else return ERROR;
}
}
下面是另一种能AC的代码：
ElementType FindKth( List L, int K )
{
int i = 1;
while(L)
{
if(i==K)
return L->Data;
i++;
L=L->Next;
}
return ERROR;
}
这里的if语句要放在链表后移操作之前，因为要判断当前结点是否满足条件，如果放在后面就会漏掉第一个值。
若能找到符合要求的值，则在while循环中就会返回内容；如果while循环结束也没找到，程序会直接返回ERROR。
补全的Read()函数代码如下：
List Read()
{
List L,p,r;
int num = 0;
L = (List)malloc(sizeof(List));
r = L;
do
{
scanf("%d",&num);
p=(List)malloc(sizeof(List));
p->Data = num;
r->Next = p;
r = p;
}while(getchar()!='\n');
r->Next = NULL;
return L->Next;
}
PTA 6-5 链式表操作集
本题要求实现链式表的操作集。
函数接口定义：
Position Find( List L, ElementType X );
List Insert( List L, ElementType X, Position P );
List Delete( List L, Position P );
其中List结构定义如下：
typedef struct LNode *PtrToLNode;
struct LNode {
ElementType Data;
PtrToLNode Next;
};
typedef PtrToLNode Position;
typedef PtrToLNode List;
各个操作函数的定义为：
Position Find( List L, ElementType X )：返回线性表中首次出现X的位置。若找不到则返回ERROR；
List Insert( List L, ElementType X, Position P )：将X插入在位置P指向的结点之前，返回链表的表头。如果参数P指向非法位置，则打印“Wrong Position for Insertion”，返回ERROR；
List Delete( List L, Position P )：将位置P的元素删除并返回链表的表头。若参数P指向非法位置，则打印“Wrong Position for Deletion”并返回ERROR。
裁判测试程序样例：
#include <stdio.h>
#include <stdlib.h>
#define ERROR NULL
typedef int ElementType;
typedef struct LNode *PtrToLNode;
struct LNode {
ElementType Data;
PtrToLNode Next;
};
typedef PtrToLNode Position;
typedef PtrToLNode List;
Position Find( List L, ElementType X );
List Insert( List L, ElementType X, Position P );
List Delete( List L, Position P );
int main()
{
List L;
ElementType X;
Position P, tmp;
int N;
L = NULL;
scanf("%d", &N);
while ( N-- ) {
scanf("%d", &X);
L = Insert(L, X, L);
if ( L==ERROR ) printf("Wrong Answer\n");
}
scanf("%d", &N);
while ( N-- ) {
scanf("%d", &X);
P = Find(L, X);
if ( P == ERROR )
printf("Finding Error: %d is not in.\n", X);
else {
L = Delete(L, P);
printf("%d is found and deleted.\n", X);
if ( L==ERROR )
printf("Wrong Answer or Empty List.\n");
}
}
L = Insert(L, X, NULL);
if ( L==ERROR ) printf("Wrong Answer\n");
else
printf("%d is inserted as the last element.\n", X);
P = (Position)malloc(sizeof(struct LNode));
tmp = Insert(L, X, P);
if ( tmp!=ERROR ) printf("Wrong Answer\n");
tmp = Delete(L, P);
if ( tmp!=ERROR ) printf("Wrong Answer\n");
for ( P=L; P; P = P->Next ) printf("%d ", P->Data);
return 0;
}
/* 你的代码将被嵌在这里 */
输入样例：
6
12 2 4 87 10 2
4
2 12 87 5
输出样例：
2 is found and deleted.
12 is found and deleted.
87 is found and deleted.
Finding Error: 5 is not in.
5 is inserted as the last element.
Wrong Position for Insertion
Wrong Position for Deletion
10 4 2 5
根据课堂代码改写的代码如下：
Position Find( List L, ElementType X )
{
List p = L;
while(p!=NULL && p->Data!=X)
p=p->Next;
return p;
}
另一种能AC的代码如下：
Position Find( List L, ElementType X )
{
while(L)
{
if(L->Data==X)
return L;
L = L->Next;
}
return ERROR;
}
List Insert( List L, ElementType X, Position P )
{
List head = L;
List p = (List)malloc(sizeof(List));
p->Data = X;
p->Next = NULL;
if(L==P)
{
p->Next = L;
return p;
}
while(L)
{
if(P==L->Next)
{
p->Next = L->Next;
L->Next = p;
return head;
}
L=L->Next;
}
printf("Wrong Position for Insertion\n");
return ERROR;
}
List Delete( List L, Position P )
{
if(L==P)
{
L = L->Next;
return L;
}
List head = L;
while(L)
{
if(L->Next==P)
{
L->Next=P->Next;
return head;
}
L=L->Next;
}
printf("Wrong Position for Deletion\n");
return ERROR;
}