动态存储分配，对固定存储进行分配，也就是说存储空间增加或减少。
13.1 （静态）链表
一般情况下，增加、删除array中的元素，要对后面的所有元素进行后移、前移，这样很麻烦。
链表，可以使数组不必频繁排序、重建。
链表link list，是一组每个结构至少包含一个成员的结构，这个成员的值是这个列表中下一个逻辑上有序结构的地址。
这个结构通过包含下一个结构的地址，在肢解领先它的结构中被链接在一起。
链表示意
#include <stdio.h>
#define MAXNAME 30
#define MAXPHONE 15
struct TeleType
{
char name[MAXNAME];
char phoneNum[MAXPHONE];
struct TeleType *nextaddr;
};
int main()
{
struct TeleType t1 = {"Acme, Sam","(555) 898 2392"};
struct TeleType t2 = {"Dolan, Edith","(555) 682 3104"};
struct TeleType t3 = {"Lanfrank, John","(555) 718 4581"};
struct TeleType *first; /* create a pointer to a structure */
void display(struct TeleType *); /* function prototype */
first = &t1; /* store t1's address in first */
t1.nextaddr = &t2; /* store t2's address in t1.nextaddr */
t2.nextaddr = &t3; /* store t3's address in t2.nextaddr */
t3.nextaddr = NULL; /* store the NULL address in t3.nextaddr */
display(first); /* send the address of the first structure */
return 0;
}
void display(struct TeleType *contents) /* contents is a pointer */
{ /* to a structure of type TeleType */
while (contents != NULL) /* display till end of linked list */
{
printf("%-30s %-20s\n",contents->name, contents->phoneNum);
contents = contents->nextaddr; /* get next address */
//(*contents).nextaddr能被contents->nextaddr取代
}
}
13.2 动态存储分配
malloc()
calloc()
realloc()
free()
malloc(200 * sizeof(int))，保留一个足够的字节数以存储200个整数
如果变量grades是一个只想整型的指针，已经被malloc()使用下面的语句创建：
grades = malloc(sizeof(int))
这个malloc()总是创建grades为一个指向void的指针，首先，得重定义grades为一个整型的地址，通过
(int *)grades;
来完成。
#include <stdio.h>
#include <stdlib.h>
int main()
{
int numgrades, i;
int *grades;
printf("\nEnter the number of grades to be processed: ");
scanf("%d", &numgrades);
/* here is where the request for memory is made */
grades = (int *) malloc(numgrades * sizeof(int));
/* here we check that the allocation was satisfied */
if (grades == (int *) NULL)
{
printf("\nFailed to allocate grades array\n");
exit(1);
}
for(i = 0; i < numgrades; i++)
{
printf(" Enter a grade: ");
scanf("%d", &grades[i]);
}
printf("\nAn array was created for %d integers", numgrades);
printf("\nThe values stored in the array are:\n");
for (i = 0; i < numgrades; i++)
printf(" %d\n", grades[i]);
free(grades);
return 0;
}
如果malloc()不能获得想得到的存储空间，它返回一个NULL。
free()函数在这个程序末端，把已分配的存储块归还给操作系统。
13.3 栈（顶部操作）（先出后进的列表）
栈是一种特殊的link list类型。
在栈中，对象只能被加到这个列表的顶部和从这个列表的顶部被移去。
入栈：PUSH，顶部＋1
动态创建一个新的结构，
原栈顶指针中的地址防盗新结构的地址字段中
填入新结构的剩余字段
把新结构的地址放入栈顶指针中
出栈：** POP **，顶部－1
把栈顶指针指向的结构内容移入一个工作区域中
释放被栈顶指针指向的结构
把工作区地址自断中的地址移入这个栈顶指针中
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXCHARS 30
#define DEBUG 0
/* here is the declaration of a stack structure */
struct NameRec
{
char name[MAXCHARS];
struct NameRec *priorAddr;
};
/* here is the definition of the top of stack pointer */
struct NameRec *tosp ;
int main()
{
void readPush(); /* function prototypes */
void popShow();
tosp = NULL; /* initialize the top of stack pointer */
readPush();
popShow();
return 0;
}
/* get a name and push it onto the stack */
void readPush()
{
char name[MAXCHARS];
void push(char *);
printf("Enter as many names as you wish, one per line");
printf("\nTo stop entering names, enter a single x\n");
while (1)
{
printf("Enter a name: ");
gets(name);
if (strcmp(name,"x") == 0)
break;
push(name);
}
}
/* pop and display names from the stack */
void popShow()
{
char name[MAXCHARS];
void pop(char *);
printf("\nThe names popped from the stack are:\n");
while (tosp != NULL) /* display till end of stack */
{
pop(name);
printf("%s\n",name);
}
}
void push(char *name)
{
struct NameRec *newaddr; /* pointer to structure of type NameRec */
if (DEBUG)
printf("Before the push the address in tosp is %p", tosp);
newaddr = (struct NameRec *) malloc(sizeof(struct NameRec));
if (newaddr == (struct NameRec *) NULL)
{
printf("\nFailed to allocate memory for this structure\n");
exit(1);
}
strcpy(newaddr->name,name); /* store the name */
newaddr->priorAddr = tosp; /* store address of prior structure */
tosp = newaddr; /* update the top of stack pointer */
if (DEBUG)
printf("\n After the push the address in tosp is %p\n", tosp);
}
void pop(char *name)
{
struct NameRec *tempAddr;
if (DEBUG)
printf("Before the pop the address in tosp is %p\n", tosp);
strcpy(name,tosp->name); /* retrieve the name from the top of stack */
tempAddr = tosp->priorAddr; /* retrieve the prior address */
free(tosp); /* release the structure's memory space */
tosp = tempAddr; /* update the top of stack pointer */
if (DEBUG)
printf(" After the pop the address in tosp is %p\n", tosp);
}
13.4 队列（顶部进，底部处）（先进先出）
入队：enqueueing放置一个新的项目到队列顶部
动态的创建一个新结构
设置这个新结构的地址字段为NULL
填充新结构的剩余字段
设置被入队指针指向的结构的地址给新创建的结构的地址
用新创建的结构的地址更新入队指针中的地址
出队：serving从一个队列移出一个项目
把出队指针指向的这个结构的内容移到一个工作区域中
释放出队指针指向的这个结构
把工作区域地址字段中的地址移到出队指针中
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXCHARS 30
#define DEBUG 0
/* here is the declaration of a queue structure */
struct NameRec
{
char name[MAXCHARS];
struct NameRec *nextAddr;
};
/* here is the definition of the top and bottom queue pointers */
struct NameRec *queueIn, *queueOut;
int main()
{
void readEnque(); /* function prototypes */
void serveShow();
queueIn = NULL; /* initialize queue pointers */
queueOut = NULL;
readEnque();
serveShow();
}
/* get a name and enque it onto the queue */
void readEnque()
{
char name[MAXCHARS];
void enque(char *);
printf("Enter as many names as you wish, one per line");
printf("\nTo stop entering names, enter a single x\n");
while (1)
{
printf("Enter a name: ");
gets(name);
if (strcmp(name,"x") == 0)
break;
enque(name);
}
}
/* serve and display names from the queue */
void serveShow()
{
char name[MAXCHARS];
void serve(char *);
printf("\nThe names served from the queue are:\n");
while (queueOut != NULL) /* display till end of queue */
{
serve(name);
printf("%s\n",name);
}
}
void enque(char *name)
{
struct NameRec *newaddr; /* pointer to structure of type NameRec */
if (DEBUG)
{
printf("Before the enque the address in queueIn is %p", queueIn);
printf("\nand the address in queueOut is %p", queueOut);
}
newaddr = (struct NameRec *) malloc(sizeof(struct NameRec));
if (newaddr == (struct NameRec *) NULL)
{
printf("\nFailed to allocate memory for this structure\n");
exit(1);
}
/* the next two if statements handle the empty queue initialization */
if (queueOut == NULL)
queueOut = newaddr;
if (queueIn != NULL)
queueIn->nextAddr = newaddr; /* fill in prior structure's address field */
strcpy(newaddr->name,name); /* store the name */
newaddr->nextAddr = NULL; /* set address field to NULL */
queueIn = newaddr; /* update the top of queue pointer */
if (DEBUG)
{
printf("\n After the enque the address in queueIn is %p\n", queueIn);
printf(" and the address in queueOut is %p\n", queueOut);
}
}
void serve(char *name)
{
struct NameRec *nextAddr;
if (DEBUG)
printf("Before the serve the address in queueOut is %p\n", queueOut);
/* retrieve the name from the bottom of queue */
strcpy(name,queueOut->name);
/* capture the next address field */
nextAddr = queueOut->nextAddr;
free(queueOut);
/* update the bottom of queue pointer */
queueOut = nextAddr;
if (DEBUG)
printf(" After the serve the address in queueOut is %u\n",
queueOut);
}
13.5 动态链表
栈、队列，只允许列表的一端被操作。
动态链表，允许任何地方添加和删除。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXCHARS 30
#define DEBUG 0
/* here is the declaration of a linked list structure */
struct NameRec
{
char name[MAXCHARS];
struct NameRec *nextAddr;
};
/* here is the definition of the first structure pointer */
struct NameRec *firstRec;
int main()
{
void readInsert(); /* function prototypes */
void display();
firstRec = NULL; /* initialize list pointer */
readInsert();
display();
return 0;
}
/* get a name and insert it into the linked list */
void readInsert()
{
char name[MAXCHARS];
void insert(char *);
printf("\nEnter as many names as you wish, one per line");
printf("\nTo stop entering names, enter a single x\n");
while (1)
{
printf("Enter a name: ");
gets(name);
if (strcmp(name,"x") == 0)
break;
insert(name);
}
}
void insert(char *name)
{
struct NameRec *linearLocate(char *); /* function prototype */
struct NameRec *newaddr, *here; /* pointers to structure */
/* of type NameRec */
newaddr = (struct NameRec *) malloc(sizeof(struct NameRec));
if (newaddr == (struct NameRec *) NULL) /* check the address */
{
printf("\nCould not allocate the requested space\n");
exit(1);
}
/* locate where the new structure should be placed and */
/* update all pointer members */
if (firstRec == NULL) /* no list currently exists */
{
newaddr->nextAddr = NULL;
firstRec = newaddr;
}
else if (strcmp(name, firstRec->name) < 0) /* a new first structure */
{
newaddr->nextAddr = firstRec;
firstRec = newaddr;
}
else /* structure is not the first structure of the list */
{
here = linearLocate(name);
newaddr->nextAddr = here->nextAddr;
here->nextAddr = newaddr;
}
strcpy(newaddr->name,name); /* store the name */
}
/* This function locates the address of where a new structure
should be inserted within an existing list.
It receives the address of a name and returns the address of a
structure of type NameRec
*/
struct NameRec *linearLocate(char *name)
{
struct NameRec *one, *two;
one = firstRec;
two = one->nextAddr;
if (two == NULL)
return(one); /* new structure goes after the existing single structure */
while(1)
{
if(strcmp(name,two->name) < 0) /* if it is located within the list */
break;
else if(two->nextAddr == NULL) /* it goes after the last structure */
{
one = two;
break;
}
else /* more structures to search against */
{
one = two;
two = one->nextAddr;
}
} /* the break takes us here */
return(one);
}
/* display names from the linked list */
void display()
{
struct NameRec *contents;
contents = firstRec;
printf("\nThe names currently in the list, in alphabetical");
printf("\norder, are:\n");
while (contents != NULL) /* display till end of list */
{
printf("%s\n",contents->name);
contents = contents->nextAddr;
}
}
语法
struct Test
{
int inNum;
double *ptPay;
};
＊ 指针＝变量
& 变量，是变量的地址＝指针
网友评论