线性表-对帆神的拙劣模仿

学习目标：

学会线性表

学习内容:

  1. 抄代码并运行. 不包括 locateElement, getElement, clearList.
  2. 自己实现 locateElement, getElement, clearList 三个函数并与我的代码比较.
  3. 实现并测试书上其它相关函数如 PriorElement.
  4. 找出帆神代码的问题, 并在数据结构 C 代码 1: 顺序表下方留言.

学习时间：

2022.4.25

学习产出：

目录

1.拙略抄写

2.定位元素的方法

3.得到元素位置的方法

4.清空元素

5.最后附上改好的全部代码

拙略抄写（过于拙略所以注释也抄了）

定义结构题

/**
 * Linear list of integers. The key is data.
 */
typedef struct SequentialList {
	int actualLength;
	int data[LIST_MAX_LENGTH]; //The maximum length is fixed.
} *SequentialListPtr;

输出线性表

/**
 * Output the list.
 */
void outputList(SequentialListPtr paraList) {
	for(int i = 0; i < paraList->actualLength; i ++) {
		printf("%d ", paraList->data[i]);
	}// Of for i
	printf("\r\n");
}// Of outputList

输出地址

/**
 * Output the memeory for the list.
 */
void outputMemory(SequentialListPtr paraListPtr) {
	printf("The address of the structure: %ld\r\n", paraListPtr);
	printf("The address of actualLength: %ld\r\n", &paraListPtr->actualLength);
	printf("The address of data: %ld\r\n", &paraListPtr->data);
	printf("The address of actual data: %ld\r\n", &paraListPtr->data[0]);
	printf("The address of second data: %ld\r\n", &paraListPtr->data[1]);
}// Of outputMemory

初始化线性表（把数组封装进结构体）

/**
 * Initialize a sequential list. No error checking for this function.
 * @param paraListPtr The pointer to the list. It must be a pointer to change the list.
 * @param paraValues An int array storing all elements.
 */
SequentialListPtr sequentialListInit(int paraData[], int paraLength) {
	SequentialListPtr resultPtr = (SequentialListPtr)malloc(sizeof(struct SequentialList));
	for (int i = 0; i < paraLength; i ++) {
		resultPtr->data[i] = paraData[i];
	}// Of for i
	resultPtr->actualLength = paraLength;

	return resultPtr;
}//Of sequentialListInit

向线性表中插入一个元素

/**
 * Insert an element into a sequential linear list.
 * @param paraListPtr The pointer to the list. It must be a pointer to change the list.
 * @param paraPosition The position, e.g., 0 stands for inserting at the first position.
 * @param paraValue The value to be inserted.
 */
void sequentialListInsert(SequentialListPtr paraListPtr, int paraPosition, int paraValue) {
	// Step 1. Space check.
	if (paraListPtr->actualLength >= LIST_MAX_LENGTH) {
		printf("Cannot insert element: list full.\r\n");
		return;
	}//Of if

	// Step 2. Position check.
	if (paraPosition < 0) {
		printf("Cannot insert element: negative position unsupported.");
		return;
	}//Of if
	if (paraPosition > paraListPtr->actualLength) {
		printf("Cannot insert element: the position %d is bigger than the list length %d.\r\n", paraPosition, paraListPtr->actualLength);
		return;
	}//Of if

	// Step 3. Move the remaining part.
	for (int i = paraListPtr->actualLength; i > paraPosition; i --) {
		paraListPtr->data[i] = paraListPtr->data[i - 1];
	}//Of for i

	// Step 4. Insert.
	paraListPtr->data[paraPosition] = paraValue;

	// Step 5. Update the length.
	paraListPtr->actualLength ++;
}// Of sequentialListInsert

/**
 * Test the insert function.
 */
void sequentialInsertTest() {
	int i;
	int tempArray[5] = {3, 5, 2, 7, 4};

	printf("---- sequentialInsertTest begins. ----\r\n");

	// Initialize.
	SequentialListPtr tempList = sequentialListInit(tempArray, 5);
	printf("After initialization, the list is: ");
	outputList(tempList);

	// Insert to the first.
	printf("Now insert to the first, the list is: ");
	sequentialListInsert(tempList, 0, 8);
	outputList(tempList);

	// Insert to the last.
	printf("Now insert to the last, the list is: ");
	sequentialListInsert(tempList, 6, 9);
	outputList(tempList);

	// Insert beyond the tail.
	printf("Now insert beyond the tail. \r\n");
	sequentialListInsert(tempList, 8, 9);
	printf("The list is:");
	outputList(tempList);

	// Insert to position 3.
	for (i = 0; i < 5; i ++) {
		printf("Inserting %d.\r\n", (i + 10));
		sequentialListInsert(tempList, 0, (i + 10));
		outputList(tempList);
	}//Of for i
	free(tempList);
	printf("---- sequentialInsertTest ends. ----\r\n");
}// Of sequentialInsertTest

在线性表中删除一个元素

定位元素的方法


/**
 * Locate an element in the list.
 * @param paraListPtr The pointer to the list.
 * @param paraValue the indicated value.
 * @return The position of the value, or-1 indicating not exists
 */
int locateElement(SequentialListPtr paraListPtr, int paraValue) {
	for (int i = 0; i < paraListPtr->actualLength; i ++) {
		if (paraListPtr->data[i] == paraValue) return i;
	}
	return -1;
}// Of locateElement

void locateElementTest(){
	int tempArray[5] = {3, 5, 2, 7, 4};

	printf("---- locateElementTest begins. ----\r\n");

	// Initialize.
	SequentialListPtr tempList = sequentialListInit(tempArray, 5);
	printf("After initialization, the list is: ");
	outputList(tempList);
	//use id draw the location
	int id,data;

	//first data
	data=3;
	id=locateElement(tempList, data);
	if(id==-1){
		printf("not find the element!!!\n");
		//TODO
	}else{
		printf("Now location of the %d element is %d\n",data,id);
	}

	//4th data
	data=7;
	id=locateElement(tempList, data);
	if(id==-1){
		printf("not find the element!!!\n");
		//TODO
	}else{
		printf("Now location of the %d element is %d\n",data,id);
	}

	//seconed
	data=5;
	id=locateElement(tempList, data);
	if(id==-1){
		printf("not find the element!!!\n");
		//TODO
	}else{
		printf("Now location of the %d element is %d\n",data,id);
	}

	//last
	data=4;
	id=locateElement(tempList, data);
	if(id==-1){
		printf("not find the element!!!\n");
		//TODO
	}else{
		printf("Now location of the %d element is %d\n",data,id);
	}

	//not find
	data=-6;
	id=locateElement(tempList, data);
	if(id==-1){
		printf("not find the element!!!\n");
		//TODO
	}else{
		printf("Now location of the %d element is %d\n",data,id);
	}
	free(tempList);
	printf("---- locateElementTest ends. ----\r\n\n");
}

测试用例结果：

---- locateElementTest begins. ----
After initialization, the list is: 3 5 2 7 4
Now location of the 3 element is 0
Now location of the 7 element is 3
Now location of the 5 element is 1
Now location of the 4 element is 4
not find the element!!!
---- locateElementTest ends. ----

得到元素位置的方法

/**
 * Get an element in the list.
 * @param paraListPtr The pointer to the list.
 * @param paraPosition The given position.
 * @return The position of the value, or  -1 indicating not exists
 */
int getElement(SequentialListPtr paraListPtr, int paraPosition) {
	// Step 1. Position check.
	if (paraPosition < 0||paraPosition >= paraListPtr->actualLength) {
		return -1;
	}//Of if
	return paraListPtr->data[paraPosition];
}// Of locateElement

void getElementTest(){
	int tempArray[5] = {3, 5, 2, 7, 4};

	printf("---- getElementTest begins. ----\r\n");

	// Initialize.
	SequentialListPtr tempList = sequentialListInit(tempArray, 5);
	printf("After initialization, the list is: ");
	outputList(tempList);
	//use id draw the location
	int id,data;

	//first data
	id=0;
	data=getElement(tempList, id);
	if(data==-1){
		printf("not find the element!!!\n");
		//TODO
	}else{
		printf("Now data of the %d element is %d\n",id,data);
	}

	//4th data
	id=3;
	data=getElement(tempList, id);
	if(data==-1){
		printf("not find the element!!!\n");
		//TODO
	}else{
		printf("Now data of the %d element is %d\n",id,data);
	}

	//seconed
	id=1;
	data=getElement(tempList, id);
	if(data==-1){
		printf("not find the element!!!\n");
		//TODO
	}else{
		printf("Now data of the %d element is %d\n",id,data);
	}

	//last
	id=4;
	data=getElement(tempList, id);
	if(data==-1){
		printf("not find the element!!!\n");
		//TODO
	}else{
		printf("Now data of the %d element is %d\n",id,data);
	}

	//not find
	id=-6;
	data=getElement(tempList, id);
	if(data==-1){
		printf("not find the element!!!\n");
		//TODO
	}else{
		printf("Now data of the %d element is %d\n",id,data);
	}
	
	free(tempList);
	printf("---- getElementTest ends. ----\r\n\n");
}

测试用例结果：

---- getElementTest begins. ----
After initialization, the list is: 3 5 2 7 4
Now data of the 0 element is 3
Now data of the 3 element is 7
Now data of the 1 element is 5
Now data of the 4 element is 4
not find the element!!!
---- getElementTest ends. ----

清空元素（需要释放一下内存）

/**
 * Clear elements in the list.
 * @param paraListPtr The pointer to the list.
 * @return The position of the value, or  -1 indicating not exists
 */
void clearList(SequentialListPtr paraListPtr) {
	free(paraListPtr);
	paraListPtr->actualLength = 0;
	paraListPtr=NULL;
}// Of clearList
void clearListTest() {
	int tempArray[5] = {3, 5, 2, 7, 4};

	printf("---- clearListTest begins. ----\r\n");

	// Initialize.
	SequentialListPtr tempList = sequentialListInit(tempArray, 5);
	printf("After initialization, the list is: ");
	outputList(tempList);

	//clear
	clearList(tempList);

	printf("After clear, the list is:");
	outputList(tempList);

	printf("---- clearListTest ends. ----\r\n\n");

	outputMemory(tempList);
}

测试用例结果 

---- clearListTest begins. ----
After initialization, the list is: 3 5 2 7 4
After clear, the list is:
---- clearListTest ends. ----

The address of the structure: 911939936
The address of actualLength: 911939936
The address of data: 911939940
The address of actual data: 911939940
The address of second data: 911939944

最后附上改好的全部代码

#include <stdio.h>
#include <malloc.h>

#define LIST_MAX_LENGTH 10

/**
 * Linear list of integers. The key is data.
 */
typedef struct SequentialList {
	int actualLength;
	int data[LIST_MAX_LENGTH]; //The maximum length is fixed.
} *SequentialListPtr;

/**
 * Output the list.
 */
void outputList(SequentialListPtr paraList) {
	for(int i = 0; i < paraList->actualLength; i ++) {
		printf("%d ", paraList->data[i]);
	}// Of for i
	printf("\r\n");
}// Of outputList

/**
 * Output the memeory for the list.
 */
void outputMemory(SequentialListPtr paraListPtr) {
	printf("The address of the structure: %ld\r\n", paraListPtr);
	printf("The address of actualLength: %ld\r\n", &paraListPtr->actualLength);
	printf("The address of data: %ld\r\n", &paraListPtr->data);
	printf("The address of actual data: %ld\r\n", &paraListPtr->data[0]);
	printf("The address of second data: %ld\r\n", &paraListPtr->data[1]);
}// Of outputMemory

/**
 * Initialize a sequential list. No error checking for this function.
 * @param paraListPtr The pointer to the list. It must be a pointer to change the list.
 * @param paraValues An int array storing all elements.
 */
SequentialListPtr sequentialListInit(int paraData[], int paraLength) {
	SequentialListPtr resultPtr = (SequentialListPtr)malloc(sizeof(struct SequentialList));
	for (int i = 0; i < paraLength; i ++) {
		resultPtr->data[i] = paraData[i];
	}// Of for i
	resultPtr->actualLength = paraLength;

	return resultPtr;
}//Of sequentialListInit

/**
 * Insert an element into a sequential linear list.
 * @param paraListPtr The pointer to the list. It must be a pointer to change the list.
 * @param paraPosition The position, e.g., 0 stands for inserting at the first position.
 * @param paraValue The value to be inserted.
 */
void sequentialListInsert(SequentialListPtr paraListPtr, int paraPosition, int paraValue) {
	// Step 1. Space check.
	if (paraListPtr->actualLength >= LIST_MAX_LENGTH) {
		printf("Cannot insert element: list full.\r\n");
		return;
	}//Of if

	// Step 2. Position check.
	if (paraPosition < 0) {
		printf("Cannot insert element: negative position unsupported.");
		return;
	}//Of if
	if (paraPosition > paraListPtr->actualLength) {
		printf("Cannot insert element: the position %d is bigger than the list length %d.\r\n", paraPosition, paraListPtr->actualLength);
		return;
	}//Of if

	// Step 3. Move the remaining part.
	for (int i = paraListPtr->actualLength; i > paraPosition; i --) {
		paraListPtr->data[i] = paraListPtr->data[i - 1];
	}//Of for i

	// Step 4. Insert.
	paraListPtr->data[paraPosition] = paraValue;

	// Step 5. Update the length.
	paraListPtr->actualLength ++;
}// Of sequentialListInsert

/**
 * Test the insert function.
 */
void sequentialInsertTest() {
	int i;
	int tempArray[5] = {3, 5, 2, 7, 4};

	printf("---- sequentialInsertTest begins. ----\r\n");

	// Initialize.
	SequentialListPtr tempList = sequentialListInit(tempArray, 5);
	printf("After initialization, the list is: ");
	outputList(tempList);

	// Insert to the first.
	printf("Now insert to the first, the list is: ");
	sequentialListInsert(tempList, 0, 8);
	outputList(tempList);

	// Insert to the last.
	printf("Now insert to the last, the list is: ");
	sequentialListInsert(tempList, 6, 9);
	outputList(tempList);

	// Insert beyond the tail.
	printf("Now insert beyond the tail. \r\n");
	sequentialListInsert(tempList, 8, 9);
	printf("The list is:");
	outputList(tempList);

	// Insert to position 3.
	for (i = 0; i < 5; i ++) {
		printf("Inserting %d.\r\n", (i + 10));
		sequentialListInsert(tempList, 0, (i + 10));
		outputList(tempList);
	}//Of for i
	free(tempList);
	printf("---- sequentialInsertTest ends. ----\r\n");
}// Of sequentialInsertTest

/**
 * Delete an element from a sequential linear list.
 * @param paraListPtr The pointer to the list. It must be a pointer to change the list.
 * @param paraPosition The position, e.g., 0 stands for inserting at the first position.
 * @return The deleted value.
 */
int sequentialListDelete(SequentialListPtr paraListPtr, int paraPosition) {
	// Step 1. Position check.
	if (paraPosition < 0) {
		printf("Invalid position: %d.\r\n", paraPosition);
		return -1;
	}//Of if

	if (paraPosition >= paraListPtr->actualLength) {
		printf("Cannot delete element: the position %d is beyond the list length %d.\r\n", paraPosition, paraListPtr->actualLength);
		return -1;
	}//Of if

	// Step 2. Move the remaining part.
	int resultValue = paraListPtr->data[paraPosition];
	for (int i = paraPosition; i < paraListPtr->actualLength; i ++) {
		paraListPtr->data[i] = paraListPtr->data[i + 1];
	}//Of for i

	// Step 3. Update the length.
	paraListPtr->actualLength --;

	// Step 4. Return the value.
	return resultValue;
}// Of sequentialListDelete

/**
 * Test the delete function.
 */
void sequentialDeleteTest() {
	int tempArray[5] = {3, 5, 2, 7, 4};

	printf("---- sequentialDeleteTest begins. ----\r\n");

	// Initialize.
	SequentialListPtr tempList = sequentialListInit(tempArray, 5);
	printf("After initialization, the list is: ");
	outputList(tempList);

	// Delete the first.
	printf("Now delete the first, the list is: ");
	sequentialListDelete(tempList, 0);
	outputList(tempList);

	// Delete to the last.
	printf("Now delete the last, the list is: ");
	sequentialListDelete(tempList, 3);
	outputList(tempList);

	// Delete the second.
	printf("Now delete the second, the list is: ");
	sequentialListDelete(tempList, 1);
	outputList(tempList);

	// Delete the second.
	printf("Now delete the 5th, the list is: ");
	sequentialListDelete(tempList, 5);
	outputList(tempList);

	// Delete the second.
	printf("Now delete the (-6)th, the list is: ");
	sequentialListDelete(tempList, -6);
	outputList(tempList);
	free(tempList);
	printf("---- sequentialDeleteTest ends. ----\r\n");

	outputMemory(tempList);
}// Of sequentialDeleteTest



/**
 * Locate an element in the list.
 * @param paraListPtr The pointer to the list.
 * @param paraValue the indicated value.
 * @return The position of the value, or-1 indicating not exists
 */
int locateElement(SequentialListPtr paraListPtr, int paraValue) {
	for (int i = 0; i < paraListPtr->actualLength; i ++) {
		if (paraListPtr->data[i] == paraValue) return i;
	}
	return -1;
}// Of locateElement

void locateElementTest(){
	int tempArray[5] = {3, 5, 2, 7, 4};

	printf("---- locateElementTest begins. ----\r\n");

	// Initialize.
	SequentialListPtr tempList = sequentialListInit(tempArray, 5);
	printf("After initialization, the list is: ");
	outputList(tempList);
	//use id draw the location
	int id,data;

	//first data
	data=3;
	id=locateElement(tempList, data);
	if(id==-1){
		printf("not find the element!!!\n");
		//TODO
	}else{
		printf("Now location of the %d element is %d\n",data,id);
	}

	//4th data
	data=7;
	id=locateElement(tempList, data);
	if(id==-1){
		printf("not find the element!!!\n");
		//TODO
	}else{
		printf("Now location of the %d element is %d\n",data,id);
	}

	//seconed
	data=5;
	id=locateElement(tempList, data);
	if(id==-1){
		printf("not find the element!!!\n");
		//TODO
	}else{
		printf("Now location of the %d element is %d\n",data,id);
	}

	//last
	data=4;
	id=locateElement(tempList, data);
	if(id==-1){
		printf("not find the element!!!\n");
		//TODO
	}else{
		printf("Now location of the %d element is %d\n",data,id);
	}

	//not find
	data=-6;
	id=locateElement(tempList, data);
	if(id==-1){
		printf("not find the element!!!\n");
		//TODO
	}else{
		printf("Now location of the %d element is %d\n",data,id);
	}
	free(tempList);
	printf("---- locateElementTest ends. ----\r\n\n");
}

/**
 * Get an element in the list.
 * @param paraListPtr The pointer to the list.
 * @param paraPosition The given position.
 * @return The position of the value, or  -1 indicating not exists
 */
int getElement(SequentialListPtr paraListPtr, int paraPosition) {
	// Step 1. Position check.
	if (paraPosition < 0||paraPosition >= paraListPtr->actualLength) {
		return -1;
	}//Of if
	return paraListPtr->data[paraPosition];
}// Of locateElement

void getElementTest(){
	int tempArray[5] = {3, 5, 2, 7, 4};

	printf("---- getElementTest begins. ----\r\n");

	// Initialize.
	SequentialListPtr tempList = sequentialListInit(tempArray, 5);
	printf("After initialization, the list is: ");
	outputList(tempList);
	//use id draw the location
	int id,data;

	//first data
	id=0;
	data=getElement(tempList, id);
	if(data==-1){
		printf("not find the element!!!\n");
		//TODO
	}else{
		printf("Now data of the %d element is %d\n",id,data);
	}

	//4th data
	id=3;
	data=getElement(tempList, id);
	if(data==-1){
		printf("not find the element!!!\n");
		//TODO
	}else{
		printf("Now data of the %d element is %d\n",id,data);
	}

	//seconed
	id=1;
	data=getElement(tempList, id);
	if(data==-1){
		printf("not find the element!!!\n");
		//TODO
	}else{
		printf("Now data of the %d element is %d\n",id,data);
	}

	//last
	id=4;
	data=getElement(tempList, id);
	if(data==-1){
		printf("not find the element!!!\n");
		//TODO
	}else{
		printf("Now data of the %d element is %d\n",id,data);
	}

	//not find
	id=-6;
	data=getElement(tempList, id);
	if(data==-1){
		printf("not find the element!!!\n");
		//TODO
	}else{
		printf("Now data of the %d element is %d\n",id,data);
	}
	
	free(tempList);
	printf("---- getElementTest ends. ----\r\n\n");
}
/**
 * Clear elements in the list.
 * @param paraListPtr The pointer to the list.
 * @return The position of the value, or  -1 indicating not exists
 */
void clearList(SequentialListPtr paraListPtr) {
	free(paraListPtr);
	paraListPtr->actualLength = 0;
	paraListPtr=NULL;
}// Of clearList
void clearListTest() {
	int tempArray[5] = {3, 5, 2, 7, 4};

	printf("---- clearListTest begins. ----\r\n");

	// Initialize.
	SequentialListPtr tempList = sequentialListInit(tempArray, 5);
	printf("After initialization, the list is: ");
	outputList(tempList);

	//clear
	clearList(tempList);

	printf("After clear, the list is:");
	outputList(tempList);

	printf("---- clearListTest ends. ----\r\n\n");

	outputMemory(tempList);
}


/**
The entrance.
 */
void main() {
	sequentialInsertTest();
	sequentialDeleteTest();
	locateElementTest();
	getElementTest();
	clearListTest();
}// Of main

测试样例：

12 11 10 8 3 5 2 7 4 9
Inserting 14.
Cannot insert element: list full.
12 11 10 8 3 5 2 7 4 9
---- sequentialInsertTest ends. ----
---- sequentialDeleteTest begins. ----
After initialization, the list is: 3 5 2 7 4
Now delete the first, the list is: 5 2 7 4
Now delete the last, the list is: 5 2 7
Now delete the second, the list is: 5 7
Now delete the 5th, the list is: Cannot delete element: the position 5 is beyond the list length 2.
5 7
Now delete the (-6)th, the list is: Invalid position: -6.
5 7
---- sequentialDeleteTest ends. ----
The address of the structure: -2146494112
The address of actualLength: -2146494112
The address of data: -2146494108
The address of actual data: -2146494108
The address of second data: -2146494104
---- locateElementTest begins. ----
After initialization, the list is: 3 5 2 7 4
Now location of the 3 element is 0
Now location of the 7 element is 3
Now location of the 5 element is 1
Now location of the 4 element is 4
not find the element!!!
---- locateElementTest ends. ----

---- getElementTest begins. ----
After initialization, the list is: 3 5 2 7 4
Now data of the 0 element is 3
Now data of the 3 element is 7
Now data of the 1 element is 5
Now data of the 4 element is 4
not find the element!!!
---- getElementTest ends. ----

---- clearListTest begins. ----
After initialization, the list is: 3 5 2 7 4
After clear, the list is:
---- clearListTest ends. ----

The address of the structure: -2146494112
The address of actualLength: -2146494112
The address of data: -2146494108
The address of actual data: -2146494108
The address of second data: -2146494104

--------------------------------
Process exited after 0.2183 seconds with return value 3221226356

Press ANY key to continue...

 

版权声明：本文为qq_61649579原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。