学习目标：
学会线性表
学习内容:
- 抄代码并运行. 不包括 locateElement, getElement, clearList.
- 自己实现 locateElement, getElement, clearList 三个函数并与我的代码比较.
- 实现并测试书上其它相关函数如 PriorElement.
- 找出帆神代码的问题, 并在数据结构 C 代码 1: 顺序表下方留言.
学习时间：
2022.4.25
学习产出：
目录
1.拙略抄写
2.定位元素的方法
3.得到元素位置的方法
4.清空元素
5.最后附上改好的全部代码
拙略抄写（过于拙略所以注释也抄了）
定义结构题
typedef struct SequentialList {
int actualLength;
int data[LIST_MAX_LENGTH]; //The maximum length is fixed.
} *SequentialListPtr;
输出线性表
void outputList(SequentialListPtr paraList) {
for(int i = 0; i < paraList->actualLength; i ++) {
printf("%d ", paraList->data[i]);
}// Of for i
printf("rn");
}// Of outputList
输出地址
void outputMemory(SequentialListPtr paraListPtr) {
printf("The address of the structure: %ldrn", paraListPtr);
printf("The address of actualLength: %ldrn", ¶ListPtr->actualLength);
printf("The address of data: %ldrn", ¶ListPtr->data);
printf("The address of actual data: %ldrn", ¶ListPtr->data[0]);
printf("The address of second data: %ldrn", ¶ListPtr->data[1]);
}// Of outputMemory
初始化线性表（把数组封装进结构体）
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
向线性表中插入一个元素
void sequentialListInsert(SequentialListPtr paraListPtr, int paraPosition, int paraValue) {
// Step 1. Space check.
if (paraListPtr->actualLength >= LIST_MAX_LENGTH) {
printf("Cannot insert element: list full.rn");
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.rn", 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
void sequentialInsertTest() {
int i;
int tempArray[5] = {3, 5, 2, 7, 4};
printf("---- sequentialInsertTest begins. ----rn");
// 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. rn");
sequentialListInsert(tempList, 8, 9);
printf("The list is:");
outputList(tempList);
// Insert to position 3.
for (i = 0; i < 5; i ++) {
printf("Inserting %d.rn", (i + 10));
sequentialListInsert(tempList, 0, (i + 10));
outputList(tempList);
}//Of for i
free(tempList);
printf("---- sequentialInsertTest ends. ----rn");
}// Of sequentialInsertTest
在线性表中删除一个元素
定位元素的方法
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. ----rn");
// 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 %dn",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 %dn",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 %dn",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 %dn",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 %dn",data,id);
}
free(tempList);
printf("---- locateElementTest ends. ----rnn");
}
测试用例结果：
---- 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. ----
得到元素位置的方法
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. ----rn");
// 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 %dn",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 %dn",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 %dn",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 %dn",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 %dn",id,data);
}
free(tempList);
printf("---- getElementTest ends. ----rnn");
}
测试用例结果：
---- 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. ----
清空元素（需要释放一下内存）
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. ----rn");
// 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. ----rnn");
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
#include
#define LIST_MAX_LENGTH 10
typedef struct SequentialList {
int actualLength;
int data[LIST_MAX_LENGTH]; //The maximum length is fixed.
} *SequentialListPtr;
void outputList(SequentialListPtr paraList) {
for(int i = 0; i < paraList->actualLength; i ++) {
printf("%d ", paraList->data[i]);
}// Of for i
printf("rn");
}// Of outputList
void outputMemory(SequentialListPtr paraListPtr) {
printf("The address of the structure: %ldrn", paraListPtr);
printf("The address of actualLength: %ldrn", ¶ListPtr->actualLength);
printf("The address of data: %ldrn", ¶ListPtr->data);
printf("The address of actual data: %ldrn", ¶ListPtr->data[0]);
printf("The address of second data: %ldrn", ¶ListPtr->data[1]);
}// Of outputMemory
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
void sequentialListInsert(SequentialListPtr paraListPtr, int paraPosition, int paraValue) {
// Step 1. Space check.
if (paraListPtr->actualLength >= LIST_MAX_LENGTH) {
printf("Cannot insert element: list full.rn");
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.rn", 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
void sequentialInsertTest() {
int i;
int tempArray[5] = {3, 5, 2, 7, 4};
printf("---- sequentialInsertTest begins. ----rn");
// 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. rn");
sequentialListInsert(tempList, 8, 9);
printf("The list is:");
outputList(tempList);
// Insert to position 3.
for (i = 0; i < 5; i ++) {
printf("Inserting %d.rn", (i + 10));
sequentialListInsert(tempList, 0, (i + 10));
outputList(tempList);
}//Of for i
free(tempList);
printf("---- sequentialInsertTest ends. ----rn");
}// Of sequentialInsertTest
int sequentialListDelete(SequentialListPtr paraListPtr, int paraPosition) {
// Step 1. Position check.
if (paraPosition < 0) {
printf("Invalid position: %d.rn", paraPosition);
return -1;
}//Of if
if (paraPosition >= paraListPtr->actualLength) {
printf("Cannot delete element: the position %d is beyond the list length %d.rn", 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
void sequentialDeleteTest() {
int tempArray[5] = {3, 5, 2, 7, 4};
printf("---- sequentialDeleteTest begins. ----rn");
// 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. ----rn");
outputMemory(tempList);
}// Of sequentialDeleteTest
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. ----rn");
// 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 %dn",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 %dn",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 %dn",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 %dn",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 %dn",data,id);
}
free(tempList);
printf("---- locateElementTest ends. ----rnn");
}
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. ----rn");
// 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 %dn",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 %dn",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 %dn",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 %dn",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 %dn",id,data);
}
free(tempList);
printf("---- getElementTest ends. ----rnn");
}
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. ----rn");
// 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. ----rnn");
outputMemory(tempList);
}
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...
